You can do it like you assumed. But your HashMap has to be templated:
Map<String, Map<String, String>> map =
new HashMap<String, Map<String, String>>();
Otherwise you have to do a cast to Map
after you retrieve the second map from the first.
Map map = new HashMap();
((Map)map.get( "keyname" )).get( "nestedkeyname" );