If it's rust stains, CLR will take care of it:
http://www.jelmar.com/CLRbasic.htm
If you can't feel the stains under your finger, then it's likely sediment from the water (source, pipes, etc) and CLR cleans it easily. Just don't breath the fumes.
If you can feel the stains when you touch them, then they could be food residue caked on the pot. That you clean with manual work and usual kitchen cleaners.
Also, you can try commercial coffee pot cleaners such as http://www.urnex.com/ to remove the rust.
Finally, if none of the above is available in your area, try Vinegar first. If that didn't work, wash off and switch to baking soda.
There is also this recipe for cleaning rust stains from aluminum pots, though I haven't tried it.