The practice of doing so is actually a field of research and the use of these words in such a manner can be classified as fillers, used while someone is busy grasping what they want to say and so on.
From Wikipedia we get a general overview of this:
Fillers are parts of speech which are
not generally recognized as purposeful
or containing formal meaning, usually
expressed as pauses such as uh, like
and er, but also extending to repairs
("He was wearing a black—uh, I mean a
blue, a blue shirt"), and articulation
problems such as stuttering. Use is
normally frowned upon in mass media
such as news reports or films, but
they occur regularly in everyday
conversation, sometimes representing
upwards of 20% of "words" in
conversation.[citation needed] Fillers
can also be used as a pause for
thought ("I arrived at, um—3
o'clock").
The idea of whether these are valid in language or not depends on whether they follow the rules of the language, and hence, can't be answered with a simple yes or no in this case. What we can say is that people do stand by the rules of syntax of their language and so can conclude that, for the most part, such 'fillers' are 'correct'.
On the other hand, there are certain individuals and industries that hold different levels of contempt towards users, and this can be appreciated; if, for instance, you were listening to the radio and the DJ incessantly hummed and hawed with (what is to the listener) superfluous speech, then the satisfaction of tuning in would be degraded.
If we examine that last part in a little detail it is easy to see the variable conclusions one could draw, either of a person or a company, based not on what is being said but rather what is in between what is being said, the gaps et cetera. I think it's safe to say that a great affinity towards this is not held by many.
To think about how it became so 'popular', I would reduce that to 'common', using the meaning of such which categorises social status. This might be a bit of a bold step, but I believe that where the above issues constrain one from committing, the lack of those constraints allows for another to become complacent and further habitually commit the act. That's a sweeping remark, I know, only skimming the surface of an idea; and there is without doubt a whole lot to delve into in order to give this thought any credibility; I, for one, think it would be an interesting line of research - right now I don't have the time or the inclination to do so, but encourage you to pursue should you care.