Mentioned in The Last Continent, this is Mad's home city. From contextual evidence in The Last Hero, this is a Duchy. The local patron God is called Noddi. A previous ruler who lacked a sense of humour was called Lord Picric. He took this out, somewhat terminally, on his Fool, Gilbert the Stupid, whose many graves around the area, some even in relatively accessible places, are now something of a tourist attraction.
Members of the Silver Horde once, apparently, fought as mercenaries for the Duke of Nothingfjord. The battle took four weeks to complete as the Duchess was working on the tapestry of the battle, and insisted on episodes being replayed until her needlework caught up with the action. This led to Mad Hamish declaring that letting the bloody media anywhere near a decent battlefield is a mistake, and they should be kept well away from the fight.
According to the booklet on exploration supplied with The Discworld Mapp, Nothingfjord was home to a race of sea-rovers who were too polite for their own good, they made appointments to rape and pillage along the coast, then wondered why their victims were never in when they called. Members of this race became great explorers under the inspiration of the Skald Lars Larsnephew, whose huge repertoire of very long sagas would inspire anyone to seek out new lands far away.
The nearest thing to a principal town is the coastal port of Herrinsmelt.