How should I introduce myself (a graduate student) at a conference?
By starting a discussion on a point of interest to both them and you. This can typically be a question, or introducing yourself and suggesting that you would like to discuss some of your results with them. But before you can get this conversation started, you'll have to give your name, and state your position, so: all of the above.

I think the best time/place to introduce yourself is at a poster session, if your conferences have some. And the purpose of these sessions is for people to discover new research and new names in their field, so that's where it is most easy to do so.

I'd suggest the following:


  Hello, my name is X, I'm a PhD student at Y in the group of Z.
  (now, you've given him enough context… time to start a discussion)
  
  
  I've read your recent papers on W, and I had a question about it which I could not really solve myself. I was wondering whether, in the diagonalisation step of your algorithm, you could use a direct-space method based on partial sampling of the matrix, rather than transform it to reciprocal space. Do you know if someone ever tried that?
  
  
  or 
  
  
  I have a poster discussing the economics of greenhouse gases' role in global warming, and how it will enable us to save on the costs of construction of actual greenhouses. I think it may be of interest to you… I'm over there in row 307, and I'd really love to get a chance to discuss this with you…
  


Scientists are curious, and the best way to approach them is to pique their curiosity…