1) Find the game you want to speedrun. It should be one of your favourites. Don't pick a game that is somewhat moderate, it will bore you even more during speedrunning, although some games tend to be much more fun when trying to beat as fast as possible instead of normal playthrough.
You should also know the game well, preferably beaten it several times, once on hardest difficulty with all collectables or secrets if there are any. And of course, you should be good at it or at least think so.
2) Search for any existing speedrun. This is crucial. You should check out Google for any speedrun made and of course Speed Demos Archive website or other speedrunning websites (Tomb Runner, High Speed Halo, Compet-N etc.). There is nothing worse than doing a speedrun, then finding a faster run that someone put on YouTube.
3) Research ways to beat the game as fast as possible. Well, a speedrun without shortcut or tricks isn't really a speedrun, so search well for engine glitches, path shortcuts and other small tricks that make things go faster. First thing to start with it is character/vehicle movement. Try to find the fastest way of movement. I recommend to watch speedruns of other games for inspiration, but definitely start with running, strafing, jumping or combined. Remember this: There is no game without a shortcut or a trick. (Here I don't count arcades, flash, logic, etc. I mean REAL games.)
[For Tomb Raider, you can find lots of useful information in the "Area 51" section of the Tomb Runner site. –Stella]
4) Strategy/planning. You should make a practice run before you start the real thing. Search for possible shortcuts, what items you are gonna need and what you can skip. This is also a time when you choose difficulty. It should be the hardest one, but that depends on your skill, patience and if it's even possible when speedrunning. Some games become easier, like Deus Ex, some become harder or next to impossible, like Far Cry.
5) Recording. Now you should figure out a way to record your run. This is easy for PC games; just use Fraps. It's harder on the consoles. You need to use a VHS or DVD player, then grab it on PC and encode it with any encoding software like VirtualDub or Avidemux.
6) Running. It looks easier than it is in reality, but real speedruns take hours and hundreds of attempts to make them look that good. If you make any bigger mistakes or even forget a route, that should be an automatic restart, but it's preferred to have better time with a mistake then a slower time without a mistake. Just don't give up after 20 failed attempts, good speedruns take a lot of patience. And always make sure you are recording.