I'm not familiar with the Mary Black recording. However, there are at least two songs bearing that title. (BTW, note that it's spelt Connolly, not Connelly.) The one you may be thinking of was written by the poet Patrick Galvin, about 1956, I think. It goes.

JAMES CONNOLLY
(Patrick Galvin)

Where oh where is our James Connolly ?
Where oh where is that gallant man ?
He is gone to organise the union
That working men they may yet be free.

Oh who then who will lead the van ?
Oh who then who will lead the van ?
Who but our James Connolly
The hero of the working man.

Who will carry high the burning flag ?
Who will carry high the burning flag ?
Who but our James Connolly
Could carry high the burning flag.

They carried him up to the jail
They carried him up to the jail
And they shot him down on a bright May morning
And quickly laid him in his grave.

Who mourns the death of this great man ?
Who mourns the death of this great man ?
Oh bury me down in yon green garden
With union men on every side.

So they buried him down in yon green garden
With union men on every side
They swore they would form a mighty union
That James Connolly's name might be filled with pride.

Where oh where is our James Connolly ?
Where oh where is that gallant man ?
He is gone to organise the Union
That working men they may yet be free.

The other one, which is perhaps even better known goes

A great crowd had gathered outside of Kilmainham
With their heads uncovered they knelt on the ground
For inside that grim prison lay a brave Irish soldier
His life for his country about to lay down.

He went to his death like a true son of Ireland
The firing party he bravely did face
Then the order rang out: "Present Arms, Fire!"
James Connolly fell into a ready-made grave.

The black flag was hoisted the cruel deed was over
Gone was the man who loved Ireland so well
There was many a sad heart in Dublin that morning
When they murdered James Connolly, the Irish Rebel!

God's curse on you, England, you cruel-hearted monster
Your deeds they would shame all the devils in hell
There are no flowers blooming but the shamrock is growing
On the grave of James Connolly, the Irish Rebel!

Many years have rolled by since that Irish rebellion
When the guns of Britannia they loudly did speak
The bold I.R.A. they stood shoulder to shoulder
And the blood from their bodies flowed down Sackville Street.

The Four Courts of Dublin the English bombarded
The spirit of Freedom they tried hard to quell
For above all the din rose the cry "No Surrender,"
'Twas the voice of James Connolly, the Irish Rebel.

I've no idea who wrote it or when, although it sounds to me a lot closer in time to the actual event. Incidentally, its tune is that which is normally associated with the Scots song Dark Lochnagar. Which is rather fitting in view of the fact that Connolly was actually born in Edinburgh.