Where did the "K" identifier prefix for US airports come from?
The letter K was simply assigned to the contiguous US by ICAO, in order to have a system with unique identifiers for world-wide use, instead of trying to adapt local system to match. The IATA codes had been in use already and possible duplicates could not be excluded. The K in US ICAO codes is there to mark the region the codes is in, see the chart below.

A good summary of how many of the airport codes have been created can be found on www.skygod.com.

Airlines use the three-letter codes internationally in their own network, Sita, for messages such as passenger loads and departure times. World ATC and weather agencies use a separate teleprinter network, the Aeronautical Fixed Telecommunications Network (AFTN), which uses a four-letter &quot;location indicator.&quot; Going from large area to actual airport, the first letter relates to the part of the world and the second letter the country. The third letter is a group of airports within that country. Most countries who use this particular convention use a letter to denote the FIR in which the airport is located. So F is Frankfurt FIR in Germany, M is Munich; P is Paris FIR, M is Marseilles. Other ways to use the third letter include identifying a group of airports with a common factor. For example, A was used in Germany for all Canadian and American air force bases. The last letter positively identifies a specific airport.
Thus Aberdeen, Scotland, has the International Civil Aviation Organization (ICAO) location indicator of EGPD—E for Northern Europe, G for United Kingdom, P for Scottish region, and D for Dyce field. Want to figure out LFPG? It's L for southern Europe, F for France, P for Paris FIR, and G for Charles de Gaulle airport. Easy!  Some are more easy to remember. The Dominican Republic codes all start with M (Central America) and D (Dominican) and then, well, see if you spot the code for international airports in Santo Domingo (MDSD), La Romana (MDLR), Puerto Plata (MDPP), Punta Cana (MDPC) and Santiago (MDST).
So if London Heathrow has two codes — and it does, LHR and EGLL — how come I've heard Chicago O'Hare only called ORD? The answer is unique to the United States and Canada. In the 48 contiguous States the ICAO code is formed simply by adding a &quot;K&quot; to the three letter code (or by adding a &quot;C&quot; in Canada). This explains why international flight plans refer to KORD, KMIA, KJFK, etc. A meeting of two rules is Key West, the FAA code is EYW (lose the 'K') and the IATA code is KEYW (add a 'K') which works great for KEY West.
Other airports within FAA jurisdiction have ICAO codes usually formed by taking two letters from the FAA name and prefixing them with PA for Alaska, PH for Hawaii, or PG for Guam. PT appears to be Pacific Trust Territories (Pohnpei, Yap, Chuuk, etc.), and there are various random other P codes like PWAK for Wake Island.
While most U.S. airports have the same three-letter location identifier for the FAA and IATA, note I didn't say all do. Scenic Sedona Airport in Arizona is assigned SEZ by the FAA and SDX by the IATA. Because for international airlines SEZ is Seychelles International Airport in Mah�, Seychelles. Another is the Hilton Head airport in South Carolina mentioned earlier. It's IATA code is HHH, but it's FAA three letter code is HXD.

Related question:
What is the methodology for assigning airport codes?