Procedurally, you could check out some of the rust or oxidized metal shaders at highend3D and deconstruct them to see how they were built. The ones you're looking for are towards the bottom of the page.

Texture-wise, do a google search on "rust textures" or "creating rust textures" or anything like that and you'll find a mountain of photoshop tutorials or prefabs, some obviously better than others. Just make sure that you make the texture tileable after it's created (using the offset filter technique for tiling images). You also want to try to keep your textures the same height and width (i.e., 128 x 128, 256 x 256, etc.) Gnomon also has some interesting tips on figuring out your resolution here.

Here's a photoshop tutorial for creating rust to get you started on the actual texture. For more realism though, I would start with a metallic texture, then use some custom brushes, and paint rusty areas onto it.