The only time I've ever got a treasure map, was when I leveled up and got it from the post office. But, that only happens every couple of levels. Is there a way I can buy or steal a treasure map from someplace without having to level up?
It is possible to find random NPCs around the map that will sell you treasure maps. Additionally I have managed to find one on a free roam mission (I believe it was a bounty for me) just on a corpse I looted. So just keep looting corpse and keep an eye on your radar for white blips. It might be a map seller.