Here is an updated view for 2014 with a brief historical explanation.
In the early days of search engines, Google seems to be the focus here and so I will speak to Google, the methods of determining the site and page subject was to evaluate several things from the links to a page, the
title tag, the header tags primarily the
h1 tag, for a period the
description meta-tag, and the content particularly the top about 200k (or so no one really knew for sure) of text for clues. Later, the entire text was examined. The only real mechanism was to measure the number of words found on a particular page and HTML elements and weigh them accordingly to determine a topic by recognizing words, phrases, and associating them with other uses to identify the topic. With this, the strength of the supposed topic was weighed using the literal count of the recognizable topic keywords and phrases. But since Google used machine learning methods, anything not easily recognizable would be simply weighed by word count at the very least. This was a good method for a time.
Then came the various methods of gaming this system.
In 2008 with the introduction of Scholar, Google realized the value of citations and began to recognize the power of hidden connections in documents not recognized before. This caused a shift in how Google would ultimately recognize topics and value of content. Scholar, as it existed, was moved into the regular Google algorithms and a shift from traditional weighting to something more analytical focusing on relationships and recognizable patterns in context began to take shape. This was a process that evolved and improved significantly over a number of years.
There is an argument over whether keyword density was ever really a factor thus raising the notion that keyword density was a myth. Both sides of the argument had merits. For a while, it was necessary to maintain a certain keyword density to compete, but too much density was 1: easily recognized for what it was, and 2: counter productive yielding in too little gain if any. The magic number has been argued of course. For a keyword to achieve an appropriate density to properly be recognized as having value would vary radically depending upon the number of words on the page leaving open speculation as to what density was optimal for any word. The fact of the matter was, that for any word to achieve the recommended percentage density (according to SEO experts at the time), the word would have to used an inordinate number of times. The longer the page, the more ridiculous the word count would have to be.
But now the game has changed.
After much earned criticisms and some not so well deserved, Google found it's way into removing keyword density as a factor though some elements of the original algorithm will seem familiar.
Keyword density is no longer a factor though keywords remain important. Instead of density, usage of keywords in links,
h1 tags (as well as other header tags), and throughout content has become important. But because citation indexing is more prevalent and has matured to such a high state, a more natural writing of the content is now required. Each word is evaluated within context to other words, some by proximity and others by relational word/phrase indexing, so that the topic and value of a page can be better determined if and only if the content was written to be read by humans and not evaluated by machines. Google moved from evaluating content like a machine exclusively with mathematical algorithms to evaluating content closer to how humans actually evaluate content which was the goal. In short, these days, even if you were to get away with it, keyword density actually has no place in how content is evaluated anymore. Sure there are some gotchas and bumps along the road. No system is perfect. But it is improving.