I have 2 shapes (see below) a circle and a shape of the US. I want to remove the part of the US that falls outside the circle. How is this possible?
This doesn't answer your question specifically (no "cutting" involved), but another less-permanent way to do this is with a clipping mask. Duplicate the circle and make sure it is above the art you want to remove.
Then, select both the circle and the art, and do Object → Clipping Mask → Make.
This will just "hide" the portion that you don't want to appear without actually cutting the artwork.
If you view the Outlines, you can see the rest of North America is still there, just hidden.
Side note: the Hawaii on your map is HUGE. ;)