If it's rust stains or other kinds of scale build up, CLR will take care of it:
http://www.jelmar.com/CLRbasic.htm
If you can't feelFrom the stains under your finger, then it's likelypictures (thanks for adding) it looks like 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 rustbuild up.
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. you may have to make a paste and let it treat for a while.
There is also this recipe for cleaning rust stains from aluminum pots, though I haven't tried it.