Follow the guide you find for RTW:

So, as the guide says, go to \data\world\maps\base folder and edit the descr_regions.txt & map_regions.tga files normally.
But, the file descr_sounds_music_types.txt is not in Rome:TW (so, not in RTW guide) because this is new file in M2TW. You have to add the name of your new province in it, like the other provinces.

Then, edit normally all the needed files, as the guide says, in \data\world\maps\campaign\imperial_campaign folder, because those files are the same both Rome:TW & M2TW.

Last, go to \data\text folder and edit the imperial_campaign_regions_and_settlement_names.txt.



And before run the game, to not forget to DELETE the following 3 files:
map.rwm & map_heights.hgt in \data\world\maps\base folder,
and
imperial_campaign_regions_and_settlement_names.txt.strings.bin in \data\text folder.

(don't worry about the 3 deleted files, the game will regenerate new map.rwm and imperial_campaign_regions_and_settlement_names.txt.strings.bin files, based on your last changes.)

Play the game and voila!