Lothian is the county/district in which Edinburgh is. Lothian is divided
in three parts: East, West and Mid. Dalkeith and Edinburgh are in MidLothian.
Saying you have a heart of Lothian is just saying where you come from.
However, there is also a 'real' Heart of Lothian:

The 'Heart of Lothian', full name 'Heart of Midlothian', is a mozaic heart
inlaid into the pavement (i.e. sidewalk) halfway up the Royal Mile in
Edinburgh, the nearest city to Fish's hometown of Dalkeith. The heart is
traditionally spat into when you walk past it, and is a symbol of local
pride. One of the Edinburgh football (i.e. soccer) teams was named 'Heart
of Midlothian' after it and Sir Walter Scott wrote a novel of the same
name last century. The Royal Mile, which is also referred to in the song
and is otherwise known as the High Street, is an, unsurprisingly, mile
long road that leads from Edinburgh Castle to Holyrood Palace in
Edinburgh. Holyrood House/Palace is the monarch's residence when he/she
visits, and the site of the annual Edinburgh Royal Garden Party. The Royal
Mile is no longer the main shopping street (that's Princes' Street), but
it is the heart of the city during the Edinburgh Festival, and is lined
with singularly picturesque buildings.

Also: Heart of Midlothian is a professional football team (soccer for you
yanks!) in Edinburgh, commonly known as Hearts.  Fish is a fan of one of
Edinburgh's other teams, Hibernian, as you may have heard on the Electric
Bear CD where he refers to one of their very rare successes.

Even more: "The Heart of Midlothian" is a novel by Sir Walter Scott. He
also wrote "Ivanhoe." Maybe you've seen the movie of that? It's very good,
and the book is very good as well. In the book, Midlothian is the name of
a prison. I don't know if this is or was an actual prison in Scotland. I
think it's possible Fish was referring to the book when he wrote the song
"Heart of Lothian," but more likely he was only thinking of the heart of
Lothian that was mentioned here earlier, which is some kind of heart
embedded in the royal mile in Scotland.

And more info on the Heart of Lothian, added later:

1. The Heart of Midlothian was a real prison, pre-dating the book, heart in
the street, football club and song. It is this prison that Walter Scott
writes about, those as far as I know the events are fictious.

2. Given the wide number of uses of the phrase (book, football, etc)
(especially in that area of Scotland) I suspect Fish is merely using it as a
form of joke - using a familiar phrase twisted to his own meaning.

3. The Scots in general are very proud of their country and their home-town.
"I was born with a Heart of Lothian" is very much an echo of this pride, and
the nationalism that Fish has supported and encouraged since going solo.

4. Finally the phrase fits in well with the albums general theme (especially
side one) of "Happy Childhood, Unhappy Adulthood". Fish spent most of his
adult life (until quitting Marillion) outside Lothian, and the song is a
reference to a more happy time. Perhaps in retrospect we can see it as the
first signs of an unhappiness with Marillion?