How do I decide what interp to I use?

Well, there's two things to consider: What weapons you plan on using, and how good your conenction is.
The hard part is what "good" means with internet connections.

(Skip down to "What interp should I use" [without quotes] if you don't want to read this technobabble.)

The first thing that comes to your mind, if you're visiting this page for advice, is probably ping. That's wrong.
Ping is only one of a handful of things that used to measure how reliable a network connection is. Two, often more important, ones, are bandwidth and jitter. Ping is important because the higher it is the more delayed your view of the game is compared to what's actually going on on the server.
This is why you can get killed by a direct grenade after you go around a corner - You never actually get around the corner on the server, because the messages your game client sends to tell the server what it's doing or where you are don't get to the server before it kills you.
The thing is, having a high ping itself doesn't make it harder to hit things. In fact, if you have exactly 100ms ping 100% of the time, the server would just have to temporarily rewind everyone's movement by 100ms whenever you shoot for the sake of detecting your hit. With slowish projectiles, you can just lead your shots more.

Why don't you have perfect hit registration, then? Why can things be jittery and hard to hit? There are usually two things to blame here: Jitter and Packet Loss, one of which is from earlier.
Packet loss is when messages between client and server and dropped alltogether. Jitter is how they always come at slightly different latencies - variable ping.
Packet loss makes the world stop for a moment before it keeps going. Jitter makes things move at slightly but rapidly changing rates. Both make things harder to hit.
Fortunately, Source Engine provides a nice way to minimize their effects on how smooth the game looks: interp.
Unfortunately, there's a world of misinformation surrounding interp. Most of the time you see people saying to set it to something based on your ping. Others have you set a single value indiscriminately of other settings, even though it's wholly dependent on them.
There is a bit of truth to these, as in most wrong things: Higher ping usually goes hand in hand with a bad connection to the server, needing more "intense" interp to smooth things out (for different but similar reasons with "distance" high ping and "bad internet" high ping), and there are "perfect settings" that while not actually perfect do generally serve well for their purpose.

Note: PVP Source Engine games tend not to lag compensate projectiles. I know that L4D2 is an exception, in some case or another. Regardless, if you're upset about being hit by projectiles that miss you while you have low ping (according to net_graph, not the scoreboard... trust me), then you should try lowering your interp.

How interp works is like this: The client recieves a certain number of messages in advance of what it shows you, and looks a certain distance into the past to render stuff. It's long and complicated, but the effect is that it slides to the newest update as it's ready in order to keep things smooth. (Really, it's a very complicated topic and it's somewhat better explained here:
So, when updates come at jittery intervals (if you took a ruler and moved every notch a short random distance it would be jittery), higher interps reduce the effective jitter by lowering the ratio of "random" time offsets to "real" time offsets. If that doesn't make sense, I'll put it a different way: You know how the difference between a two year old and a five year old is a lot more than the difference between a 20 and a 23? It's something like that.

The "problem" is that the default interp with valve's games is unfit for competitive or intense play in games with fast movement, like TF2. Rockets come out late, rockets hit you early, everything is just generally delayed. Personally, I can tell the difference between 15 and 50 ms of interp - it's not a lot, but it's there. I can't imagine playing on 100ms again.
The thing is, some classes actually suffer a lot when using harsh, jittery interp settings meant for getting your rockets out of your barrel as soon as possible, like scout. So you can't just plug in some stuff into the console and expect to get the best of everything. Some (all?) of the networking settings also don't get saved to config.cfg, which means that unless you set them through autoexec.cfg or individual class configs, you'll have to set them every single time you launch the game.

What interp should I use?

For starters, these are the net settings from Chris's FPS config, as of mid Jan 2013 (notes added by me):
// Good connection //cl_cmdrate 66 //cl_interp 0 //cl_interp_ratio 1 //cl_lagcompensation 1 // DO NOT EVER CHANGE THIS //cl_pred_optimize 2 // DO NOT EVER CHANGE THIS //cl_smooth 0 // Reset these to defaults if you don't like how the game acts when you rocketjump or get knocked around //cl_smoothtime 0.01 // Reset these to defaults if you don't like how the game acts when you rocketjump or get knocked around //cl_updaterate 66 //rate 60000 // Bad connection //cl_cmdrate 40 //cl_interp 0 //cl_interp_ratio 2 //cl_lagcompensation 1 //cl_pred_optimize 2 //cl_smooth 0 //cl_smoothtime 0.01 //cl_updaterate 40 //rate 35000
"Good connection" is what you want to start with. Use "bad connection" if you have dialup. Just uncomment every line aside from the block's header (remove the first // from each line).

Now, for improving hitreg or making rockets come out sooner, depending on which you picked above: From personal experience and theorycraft backed by some level of wealth of knowledge of TF2's - and in general - networking, I ended up with some settings that work well almost anywhere I go, regardless of server settings or most of my connection trouble (and I have Time Warner).
// To use these, uncomment the ones you want and put them in class.cfg files. // For example, if you want to use the alternative "harsh" setting on Soldier, you would uncomment it and put "net_harsh2" near the top of soldier.cfg (after any "exec" statements). // Harshest timing oriented interp settings -- uncomment only the one appropriate for you //alias net_harsh "cl_interp 0.0152; cl_interp_ratio 1" // for updaterate 66 //alias net_harsh "cl_interp 0.025 ; cl_interp_ratio 1" // for updaterate 40 // You should use this for projectiles, the flamethrower, and feigning. // On LAN, this setting is king. I think. Someone smart give me feedback after trying it and the below "harsh2" one. // Alternative "harsh" interp //alias net_harsh2 "cl_interp 0.0182; cl_interp_ratio 1.2" // for updaterate 66 //alias net_harsh2 "cl_interp 0.03 ; cl_interp_ratio 1.2" // for updaterate 40 // Use this instead of the above if you experience rockets "warping" through scouts, microstuttering animations, or other unpleasant jitter when using the above. // Normal settings //alias net_normal "cl_interp 0.033; cl_interp_ratio 2" // for updaterate 66 //alias net_normal "cl_interp 0.05 ; cl_interp_ratio 2" // for updaterate 40 // Use this in most cases, or if you don't know what else to pick. // "Soft" settings (hitreg oriented) //alias net_soft "cl_interp 0.05 ; cl_interp_ratio 2" // for updaterate 66 //alias net_soft "cl_interp 0.055; cl_interp_ratio 2" // for updaterate 40 // This is the safest "comp" setting. If you're experiencing trouble, use this. If you still have trouble, go back to defaults. // Also, use this on things that "can not" miss or are especially susceptible to "shitreg" for you, meaning sniper rifles and (for me) scout weapons. // Default interp settings //alias net_default "cl_interp 0.1; cl_interp_ratio 2" // Fundamental settings -- take care // cl_lagcompensation 1 // DO NOT EVER CHANGE THIS NO MATTER WHAT ANYONE EVER SAYS EVER cl_pred_optimize 2 // DO NOT EVER CHANGE THIS cl_smooth 0 // Reset these to defaults if you don't like how the game acts when you rocketjump or get knocked around cl_smoothtime 0.01 // Reset these to defaults if you don't like how the game acts when you rocketjump or get knocked around // Default smooth settings, in case you need them //cl_smooth 1 //cl_smoothtime 0.1
You should be able to figure out how to apply these. Ask someone if you don't. There's also a thing where people change their interp when they change their weapons, with special binds. I don't know anything about it, I don't have any experience using it, but if it doesn't cause any problems then it's a good idea. Don't get me involved, though.