There is always a lot of confusion about this concept. (And the naming does not help!). The other answers present so far are not correct.
Firstly, we have to understand that the underlying problem (or search space) is almost always represented as a graph. So, the difference is not whether the problem is a tree (a special kind of graph), or a general graph!
The distinction instead is how we are traversing to search for our goal state. It also includes whether we are using a list or array (often called the closed list) or not.
So, the basic differences are
If doing graph search, keep a "closed" list, that is, a list of nodes where the search has been completed.
If doing a tree search, we don't keep this closed list.
The advantage of graph search obviously is that if we finish the search of a node, we will never search it again, while we may do so in tree search. The disadvantage of graph search is that it uses more memory, which we may or may not have.
So, there is a trade-off between space and time when using graph search as opposed to tree search (or vice-versa).
Now, about the naming.
Graph Search is called graph search, because when we observe the traversal structure, we observe a GRAPH, that this node leads us to the other node that we saw before, etc, etc.
Tree search is called a tree search, because when we observe the traversal structure, we observe a TREE. We observe a tree, even if the underlying problem structure is a graph. This is because when we observe a node, we have no recollection of having seen it earlier, we don't store that list, etc. So, the same node in the underlying problem structure can appear as multiple times (as different nodes) of the tree.