Of course the could not know for sure, but they had three clues:
1) Gordon had been in Blackgate as a prisoner, but he never saw the first guard:
Gordon: How long have you worked here?
Fake guard 1: Two years, thereabouts.
Gordon: I was in Blackgate for a time.
Fake guard 1: We must not have overlapped. Here? As a guard?
Gordon: As a prisoner.
Fake guard 1: Oh, yeah. Heard about that.
2) The guards did not go throw maximum security section (something which maybe was custom, as Gordon knows the place...) and gave a cheap excuse for that:
Gordon: Is there a reason why you're not taking us through maximum security?
Fake guard 1: Prisoners are in the yard this time of day. Been some changes since you were here.
3) Gordon read the name tag "McCloskey" on a guard uniform, but the guard was not the McCloskey he knows:
Gordon: "McCloskey." That's funny. I know another J. McCloskey who works here.
Fake guard 2: My cousin. Gets confusing sometimes.