Does it matter if the databases are compatible with one another (i.e. all
on oracle etc.)?
As others have noted, the systems (yours as some kind of aggregate publisher 'broker service', your potential 'clients' who publish the 'available seats', and the potential 'customers' who price and 'reserve a seat') would not generally know anything about the underlying databases, and each would only know about some application service level interface of encoded function calls and respective return values.
Your system might use several differenet databases, each specially purposed (relational data, documents, or others depending on needs and acceptable tradeoffs), and each with potentially multiple copies of itself (redundancy/load balancing). Most vendors specialize in databases with one overall purpose or type, so it is possible you will have not only more than one type or kind of database for each particular purpose, but also as a result use more than one vendor or brand.
Just how big a project is this?
Compared to what? In what terms and to what extent?
Every project, big or small is essentially accomplished by breaking the work up into chunks, whether you prefer phases, iterations, increments, sprints, episodes, or some other lingo. Rome wasn't built in a day, and neither was SABRE or any other similarly purposed system. How much can you build in the first 'day' will depend on what resources you have supporting you, in terms of people (and their talent and dedication), dollars, infrastructure (physical assets for production and processes that effectively and efficiently manage that production), and at the very least, tentative clients (to name a few).
In order to get the supporting resources, you'll need both a business and a technical plan that lays out purpose and intended value, for the initial 'days' of the project, and in the later parts of the project, if it so endures. So essentially, you'll need to determine, in your specific case why and how, value will be present in 'day 1' of the system (what is going to be fundamentally the core features -- the system essence), and how many 'days' before your service is some how more valuable than what existing services or processes can offer (regardless of whether it shows greater value than an internal system of the client, or a competing service from another third party broker).
The technical complexity isn't trivial, but it is not a completely unexplored problem space, in general (when speaking of the elements of both a reservation system, and a reservation system using aggregation or brokerage features). The specific domain, and clients, without knowing more, is what makes this question impossible for anyone here to answer with any clarity. Perhaps the most obvious hurdle would be if the clients used obscure systems internally, and further have no method of externally accessing or publishing their information to your system, as that might put the burden on you to help them build that publishing mechanism, and consequently, giving the the respective reservations back to the client, if they have to this point no means of processing 3rd party reservations.
The second most obvious technical hurdle would be client specific reservation rules. Each client may use unique rules when processing a reservation request from a customer. You probably won't be able to get clients to harmonize their rules in order for all clients to use the same rules, so your system may have to, in a sense, duplicate and honor those rules in code, and potentially make them appear harmonious to users so is not to induce a sense of favoritism for one client over another on your part. Unintended or otherwise.
The hardest part will change as time goes on. Initially, getting clients on board (willing and financially supportive), and integrated (fully able to use all advertised features of your service from a client perspective) will be the hardest parts.
As your service become more popular with customers and clients, reaching a certain system maturity, you will experience infrastructure challeneges and to some degree further business challenges: the system will need to handle more users, more users at precisely the same time, more users with specific needs (cultural issues like language/translation, physical issues such as audio or visually impaired), public exposure and political/legal issues, support issues reported by both users and possibly clients for pecularities (technically, this might be called 'edge cases' that you previously hadn't considered or valued high enough to fully explore and implement). Ad nausium.
On top of that, in essence, a 3rd party reservation system is creating a market place, and any market place will face competing interests. Some things your clients want will be unpopular with customers, and vice versa. Some things a particular client wants will break usability or feasability for another client.
It seems relatively straightforward to someone who's not a database
programmer, but I totally know that's
naiive. If my company were working to
build a service like this (again, not
for airline seats but the mechanism is
very similar) what would first steps
be?
The first step in creating a brokering system, is to ensure there is adequate interest from potential clients to move forward. If no one is interested in playing, it may not be worth pursuing. For the airlines, I am fairly certain there are strict contracts or service agreements that lock them in relationships between brokers and clients, so penatrating a market like that would mean potentially sitting on the sidelines until the contract is up for renewal, or worse.