Today I have been tuning a stored procedure in SQL Server 2005 where the execution plan showed a key lookup.
Let me first answer the question what a key lookup (aka Clustered Index Seek - before SQLServer 2005 R2) is:
If you compare a database table with a book, then the table of contents is the clustered index and the index at the end of the book is a nonclustered index. Note that the latter does not only consist of keywords, but also has references to the page numbers (without them the index would be quite useless).
A nonclustered index is very similar: it consists of the values of the chosen columns plus a reference to the entire row in the table.
A key lookup is the equivalent of the process of selecting the corresponding page to a keyword, i.e. if an index does not contain all columns a select statement needs a second step has to be performed which selects the entire row to be able to serve the missing columns.
Usually, a key lookup within an query execution plan is a sign that the query could (should) be optimized (at least if a considerable amount of rows have to be looked up).
Getting rid of key lookups is usually easy: "Covering indexes" (indexes with all the selected columns) or included column indexes will do the trick.