The Korean language is great fun to learn. It is logical and systematic. You can learn Hanguel, the Korean script in about a week, and once you have learned it, the pronounciation of words is a lot easier.
The fastest technique for actually learning to speak basic conversation Korean (or any other language) I have found is the pimsleur method. You only need to do a search on google for “korean pimsleur” to find any number of suppliers.
To get you started with Hanguel and grammar, I would recommend Elementary Korean by Ross King and Jaehoon Yeon. This book is accurate and uses Hanguel scripts. Try to avoid books which focus primarily on romanisation, as it is easier to first learn the Hanguel and read the script.
Throughout the process of learning Korean from audio and books, I also had a lot of help from a Korean tutor. You may also want to check out classroom style learning, but I would recommend it as in addition to a tutor and self-learning.
KoreanClass101.com also has an excellent set of Audio, Video and PDF lessons, and also has guided learning if you would like to be further assisted.
TalkToMeInKorean.com has a regular blog with free Audio and Video lessons, along with PDFs and a great community for learning. They also have a Twitter feed at http://twitter.com/ttmik and a place to find native speakers at www.harukorean.com.
KoreanWikiProject.com is a good resource on Hangeul.
www.memrise.com is great for memorizing vocabulary.
Web-based learning is also good, and there are several sites out there which provide free web-based Korean teaching. KOSNET and TeenKorean are excellent sites to try out, and there are more links below:
There are also some TV programs teaching Korean. The most well known is probaly Arirang TV’s Let’s Speak Korean.
When you have mastered the basics, there are a good number of books to move to, including the second part of Elementary Korean, Continuing Korean by Ross King and College Korean by Michael C. Rogers.
Also, getting as much Korean through music, video, tv shows, etc can help.
I hope this helps you learn Korean!
I have found these resources greatly helpful in my continuing learning experience.