As others have mentioned in the comments, this is covered by a well-known mathematical theorem called The Four Colour Theorem. Any map can be coloured as you describe using only four colours. The actual algorithm, though, sounds rather complex.
This answer on Stack Overflow gives an easier algorithm that will use at most five colours.
The four-color mapping algorithm is very complex, with 1476 special cases that you have to handle in your code. If you can spare one more color, the five color mapping algorithm will meet your requirements, is much simpler, and there is a nice write up on it at devx.com.
As a brief summary of the algorithm, the strategy is to find a region whose colour would be obvious if the rest of the map were already coloured. Then "remove" that region from the map and repeat the process until the map is empty. If you kept track of the order you removed the regions, you can now add them back in the reverse order, choosing colours as you do so.
To see the two rules for choosing a region to remove, see the detailed write up.