In order for the app to sync through iTunes you must go to the Apps syncing page (only available when the iPad is plugged in and selected)' turn on syncing (if off) and make sure the app is checked.
If you did not have app syncing turned on, then right click on the iPad under the Devices list and choose Transfer Purchases first. This will copy all you apps to iTunes and prevent them from being removed the next time you sync (after having turned on app syncing).
It is odd that the App Store is saying the app is installed though. You might want take another thurough look for it on the iPad first. You can use the Search to see if it as hiding somewhere (tap the Home button when on the left most Home Screen).