Building graph from database structure to implement A* algorithm?

Look into pgRouting, an extension to PostGIS that enables routing support.

I suggest to have a look at

• the osm2pgsql specific
  • line schema description
  • database layout
  • OSM wiki
  • general docs and command line docs
  • style file
  • spatial analysis example
• the OSM tags, very intensively, to be able to identify what you are looking for
  
  
• your database structure after import

To start with, the database will (at least, read about slim mode at one of the above links) contain four tables:

1. planet_osm_point
2. planet_osm_line
3. planet_osm_roads
4. planet_osm_polygon

but you have almost full control over how the tables are structured (specifically what tags will be imported as columns or if and how they will be added as hstore key/value pairs) via the style file!

Now, getting this done properly might help you reverse geocoding the user input to a set of features. OSM data however has a very complex and very exhaustive feature/relation/tag system and you will most likely end up with a dozen different features for 'Airport A' if not meticulously specified or limited further.

A much greater pain in the will be to create the routing graph. OSM road line features by themselves are far from topologically correct and will have hundreds of thousands of dangling ends and unconnected segments and whatnot, and countless road types and restrictions coded in the tags...honestly, if I were asked to do that for an area larger than my backyard, I would go get myself fired.

Why the gloomy tone? There were great minds at work for you to have it easier!

I strongly recommend you do have a look at pgRouting, as @akadouri suggested - especially at osm2pgrouting (note the patch at the bottom of the page), which will create that graph for you based on a pgRouting-friendly (but very rational) schema strucure.
There's also OSM Nominatim, which does all the tedious reverse geocoding search implementation for you. From there, it´s 'merely' a question of identifying the closest node as an entry/exit point for your routing algorithm...

You can still go and implement your A* yourself alright, but use the very useful routing and searching data structure that is provided by those tailored tools.