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" );