Why should it? If you want to iterate the keys, you have the keySet() method. If you want to iterate the values, you can use the values() method. If you want to iterate the key-value-pairs, you have the already mentioned entrySet() method.
Sun could have made Map extend Iterable, but that would require that Map itself should have an iterator() method. Imagine all the custom Map implementations that would be broken. It's bad enough they did that with the java.sql interfaces.
Besides, you can iterate over the map by using keySet(), entrySet() or values() - that's 8, 10 or 8 extra characters. Is that so much?
I have suggested that Sun implement the enhanced for loop for Maps as well:
Sun said that this wouldn't be implemented before Java 7 (which is logical), and by then it can most likely be implemented using closures. Therefore, don't expect to see it at all, so you'll be stuck using Map.Entry: