The social network paradigm works best for me when explaining to new people.

  You know how Facebook tracks your friends, and the friends they have, and friends and friends, well that kind of relationship can be called a 'graph'

Once you talk about that, I then try to get them thinking about things in a different way.. such as:

  Take this cup sitting on this table... we could say that in the same way that two friends are connected.. that the cup is also connected to the table.

  Which means, the cup is two connections away from the floor!

That is a good real world example that people can get..

  Then as you look around the room, look at how things are connected to what they touch... 
  
  It's possible to build a pretty cool graph that represents those connections just by following the paths you can see around the room.

Then you can talk about how that graph is one where things are linked by touch.. and what are other ways we could represent connections... for example, what would it look like to draw a graph of what object can SEE another object. How different that graph would be.

It's enough to get ppl thinking differently and have a high level view of Graphs