How do you search a graph?
Interviewer was probably fishing for words like: preorder, inorder, postorder traversal and depth-first versus breadth-first.  I am thinking of traversal as simply having an iterator over the graph that returns some vertices and edges in some particular order.  As Richerby says, you could fill books with all the various ways that this could happen.

As for searching graphs, if they didn't mean traversal; then they probably meant searching for subsets efficiently: If a graph is known to have implicit structure (ie: find all edges in: 192.168.4.0/24 -> 10.0.3.2/24 by hour, etc), then various kinds of searches over src/dst/time are often possible.  Facebook/Twitter, etc are utterly gigantic graphs of "at time T, A says X to B".