Hi I'm starting to work on this project where I need to have a picture (map of the US) and then I need to circles of different sizes on the map at different locations. Something like this: http://www.npr.org/templates/story/story.php?storyId=110997398
What's the best way to go about doing it? I've never dealt with Java 2-d but I'm guessing that's what I should use.
Yes, Java 2D should be exactly what you need, and Sun has some really good tutorials for it.
If you search around you can find lots of Java 2D game tutorials (like this one) as well. They might be a little more interesting to learn from, and they demonstrate the same features that you're looking for.
Hope you don't have to be to accurate, because a circle on a sphere (aka 'world') doesn't look like a circle on 2-D and a 2-D circle is something else in world coordinates.
If it's just for fun and training, you could continue with drawing 2-D circles on the projected map but if you need to draw 'real' circles on the world, you should use a library with the power to transform a shape to any projection.
Last time I used OpenMap and it was pretty easy.