If the logbook for an aircraft is lost, how does one replace it? Is the airplane still airworthy?
In order to state the plane is airworthy you must be able to show that all AD's have been complied with and that the aircraft is within annual (or 100 hour) inspection; these proofs are typically found in the logbook so no, without the logbook your aircraft is probably not airworthy. It may be possible to fly the plane legally in the US anyway if you receive authorization from your FSDO (which, I believe, would be a "ferry permit").
It's not legally required that your logbook be complete to the beginning of time, just that it shows the current requirements are met (along with the signatures/cert numbers of the AI's that are stating them to be met). However, an incomplete logbook is very important from a resale point of view. Not having complete logs will make a plane very difficult to sell and will certainly affect the price most purchasers would be willing to pay.
As mah pointed out, if you lose all your logbooks your aircraft/engine/propeller/avionics are no longer airworthy because they lack the documentation of required inspections, AD compliance, etc.
Everything is still "airworthy" in the sense that the aircraft doesn't know anything about paperwork and will happily fly, and getting a special flight ("ferry") permit from the FAA so you can take it to a mechanic to fix the paperwork will be pretty easy, but if you just go flying and something goes wrong the FAA and your insurance company will be most displeased about the lack of required paperwork.
In addition to the aircraft turning into a paperwork-pumpkin two things happen when you lose logbooks:
The value of the aircraft drops (I've seen aircraft selling for 30% less because of missing logs)
You have to "reconstruct" the aircraft's history and demonstrate compliance with all ADs and required inspections (an annual, an ELT check, a transponder check, a pitot/static check for IFR, etc...)
There's really not much you can do about #1 -- Logbooks are the history of the aircraft (and engine, propeller, avionics, etc.), and someone buying an aircraft is going to want to know that history.
How much a missing logbook matters is a matter of the buyer's personal opinion and what's missing. For example, I bought a plane missing Engine Log #1 (of 3). The engine has had two overhauls by well-known shops, one documented in Log #2 and one recently in Log #3, so my mechanic and I were not too concerned about the contents of Log #1.
Had the first airframe log been missing (which documents the plane's life as a flight school trainer in Florida) there would have been a more substantial impact on the aircraft's value.
As far as #2 goes, "reconstructing" logs is usually pretty hard.
If you're the first owner, you've always used the same shop, and your mechanic keeps meticulous records they may be able to print you out a replacement log of everything that's ever been done to the aircraft and sign it off with no sweat.
If you're not the first owner but everyone who's owned the aircraft kept meticulous records (shop invoices, etc) you still have the history even if it's not in "logbook" format -- it won't satisfy the FAA, but it will make the process of inspecting the aircraft and determining its airworthiness a little easier for your mechanic.
If you're not in either of those situations your mechanic is going to have to give the aircraft a thorough going over (in addition to conducting an annual inspection they will need to verify that every AD has been complied with (or doesn't apply). That can be a very time-consuming (and expensive) process - particularly if there are many "inspection" ADs.
Other details about the aircraft's history can usually be reconstructed from your national aviation authority & accident investigators (in the USA you would do an N-number & Serial Number search in the NTSB aviation accidents database, and request the aircraft record from the FAA which will include things like FAA Form 337 for major repairs, alterations, and STCs.
An aircraft must have a type certificate to legally fly in the US. This certificate signifies the aircraft's design passed all FAA requirements. Any alteration to the aircraft (including significant repairs) requires a supplemental type certificate, an FAA issued document. This being aviation, everything is an acronym. STCs amend the original TC. These STCs are filed with the FAA and copies are available to anyone.
Modifications must be installed by a certificated (FAA speak for 'licensed') airframe and powerplant mechanic, an A&P - another acronym. Powerplant refers to the aircraft's engine(s). Whenever a mechanic works on an airplane, she must make a logbook entry stating the what work was performed. The entry must include her mechanic's certificate number. Every US airplane must have an airframe logbook. If the airplane has engine(s), each engine has its own logbook. If an engine has a propeller, another logbook.
Assuming you are still reading this... Each part installed as part of the STC installation must have evidence it was manufactured properly. This means it was made by an authorized manufacturer and that manufacturer attests the part complies with the necessary specifications. This is the 8130 form, also called a 'yellow tag.' Some are born yellow, whereas the non-yellow ones tend to turn yellow anyway.
Airplanes are imperfect machines. From time to time, the imperfections are found. When the issue is moderate, the manufacturer issues a service bulletin. These are generally not mandatory. If the issue is serious, the FAA issues an airworthiness directive. Did you guess SB and AD? You would be right. Airworthiness directives are mandatory. Normally, they must be addressed within a certain number of flight hours. In severe cases, they must be complied with before the aircraft can be flown again, although often the aircraft is legal to fly one time to a maintenance facility. These directives can be one-time (replace this bolt with that longer one) or recurring (inspect this part for cracks every 100 flight hours).
FAA regulations also require a complete annual inspection of the aircraft. This must be performed by a super-experienced A&P mechanic, one with 'inspection authorization'. Yes, this is an IA. The inspection must follow the aircraft's FAA approved maintenance manual. The results of the inspection are documented with entries in the various logbooks.
The altimeter system must be tested every two years if the aircraft will be flying under instrument flight rules. This is IFR, and is flight without 'visual reference to the ground' as in flying in clouds, without seeing the sky, horizon or ground. From the front office (aviation-speak for the cockpit), it looks like someone covered all the windows with white paper, like a closed storefront. Anyway, This test must also be logged.
All of these logs are not required to be in the plane, but they must be reasonably available for inspection if requested by an authorized person (usually an FAA representative known as a 'Fed'). Without these logbooks, the fed will issue a citation (ticket) and probably suspend the pilot's flying privileges.
It is interesting to note the pilot is ultimately responsible. The owner, as far as the FAA is concerned, has little responsibility. Although the owner may be sued in criminal court, the pilot will receive the FAA's wrath.
So, if you lose your airplane logbooks, what do you do? You can request the type certificate and STCs. You must then reconstruct as many records as possible. If you cannot prove compliance with airworthiness directives, you must re-perform the ADs.
All of this will be very costly. It may be cheaper to sell the engine and avionics. And scrap the plane.