It is a big airport, but we have had no problems flying into Orlando International Airport in 18 years of travel with DD and her wheelchair (she 21 and got her first wheelchair when she was not quite 3). We always gate check her wheelchair and have not had a problem with getting it back at the gate when we arrive. The last few times, we have also used an aisle chair (we are getting older and she is not getting any lighter). We reminded the flight attendant that we needed one so that it was there when our plane landed.
When you go to the link that OneLittleSpark posted, look at the menu items on the left side of the page. Under the Passenger Terminal menu, there is a link to a map. When you first look at it, it sounds much more confusing than it actually is.
There is a terminal building, which has one side called the A side and the other is called the B side. They are both connected together and you can walk from the A side to the B side if you want. Each side has its own Security, Baggage, car rental and check in areas. Certain airlines fly out of the A side and others fly out of the B side.
The terminal is wheelchair accessible and there are Companion Restrooms throughout, as was already mentioned.
The gates are not attached to the terminal. Certain gates are A side gates and others are B side gates. There is a tram to take you from the gate to the same side of the terminal, so the tram from the A gates take you only to the A terminal.
The trams are wheelchair accessible and are very much like the WDW monorails, except not so high in the air. The doors open very wide and there is only a small flat gap, so it's no problem to push a wheelchair on and off the trams. They are very efficient and leave every few minutes, so you will probably not have to wait more than 5 minutes for a tram. One hint: you enter on one side and you will leave the tram on the other side, so pull into the tram and face the doors on the opposite side because that's where you will get out.
Also, on the link that OneLittle Spark posted, under the Passenger Terminal menu, there is a link to that says Arrival Walkthru. That has pictures and shows many of the things I mentioned about the trams. It also shows the differences for International Travelers (I can vouch for the accuracy of the information for general travelers, but since I have never come in there from overseas, I can't tell you if they missed mentioning anything. Looks pretty complete to me though).