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.
It's important to know what an aircraft's logs are for - what they evidence, to understand why it's such a big deal when logbooks are lost.
To legally fly in the US (and UN/ICAO member territories), an aircraft must have a valid Type Certificate. This certificate signifies the aircraft's design meets legal requirements. Alterations, including significant repairs, require a Supplemental Type Certificate. STCs amend the original TC. STCs are filed with the aviation authority, and can be requested by anyone.
Modifications must be installed by a certificated A&P, aviation-speak for 'licensed' airframe and powerplant mechanic. Whenever a mechanic works on an airplane, they must make a logbook entry describing the work performed, the procedures followed, and the result (was the work accomplished successfully). The entry must include their certificate number.
The Type Certificate is valid only when accompanied by a logbook related to the airframe's serial number. So, every airplane must have an airframe logbook. If the airplane has engine(s), each engine must have its own logbook. If an engine has a propeller, the propeller gets its own logbook, too.
Each part installed in accordance with the STC installation document must be manufactured properly. This means it was made by an authorized manufacturer (PMA) and that manufacturer attests the part complies with the necessary specifications. Compliance is indicated by the 8130 form, commonly called a 'yellow tag'. They used to be born yellow, but given the age of most general aviation aircraft, most turn yellow in time.
Airplane designs are imperfect. These design flaws are usually found in mundane ways, but sometimes they make the news. When the flaw is moderate, the manufacturer issues a service bulletin, which is highly recommended, but not necessarily mandatory. If the imperfection is serious, the FAA issues an airworthiness directive, usually referring to the service bulletin. Airworthiness directives are mandatory, and must be addressed within a certain number of flight hours or some similar measure. These directives can require a one-time effort (e.g. replace a bolt with a differently spec'd bolt) or they can be recurring (inspect this part for cracks every 100 flight hours).
FAA regulations also require a thorough annual inspection of the aircraft. This must be performed by an extra-experienced A&P mechanic, one with 'inspection authorization'. The inspection must follow the aircraft's FAA approved maintenance manual. The results of the inspection are documented with entries in the various logbooks, including which revision of the manufacturer's inspection procedure was followed.
If the aircraft will be flying under instrument flight rules, the altimeter system must be tested every two years. This test must also be logged.
Although all of these logbooks are not required to be in the plane during flight, they must be made available for inspection if requested by an authorized person -- usually an FAA representative. Without these logbooks, the fed will issue a citation and possibly 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 civil 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 attempt to reconstruct as many records as possible. You can review your emails and invoices. You can contact the places you purchased repair parts. However, if you cannot prove compliance with applicable airworthiness directives, you must re-perform the procedures required by the AD - like replacing the bolt, or inspecting the wing spar for cracks.
All of this will be costly, even by aviation standards. For old aircraft without historic value, it can be better to sell the plane for parts.