Back-story : 2002 Korea/Japan World Cup
Before the 2002 World Cup, the average person outside of Korea probably had very little awareness of Korea; the World Cup made a big difference and set the scene for more awareness of Korean culture overseas. Initially this was more noticeable in the success of some Korean films, such as Oldboy, whose success then in turn further enhanced overseas interest in Korea.
Given South Korea's geographic situation - a 'Shrimp Between two Whales' - and strong desire to develop economically, it has been seen as advantageous for Korean culture to be viewed positively worldwide. The Government has been very supportive of 'Hallyu' - the 'Korean Wave' of exported film, tv series, and music
See section on Government Support of K-pop: https://cross-currents.berkeley.edu/sites/default/files/e-journal/articles/oh_lee_0.pdf
Evolved for internet age
South Korea's domestic internet technology is among the most advanced in the world - they had speeds 10-15 years ago that others in the world are only just getting now. The rapid growth in the music industry has taken place in a context where streaming and filesharing have been widespread, so the business has long taken a lot of its cash from appearance and sponsorship / tie up fees.
Talent Pool and Development
Young Koreans study really hard. After school is over they will go for another few hours to study more music, maths, English, sports... so there are some very talented young kids who are already have a lot of the raw skills needed to do the job of a pop star by their early teens. These kids get signed up and developed further to the point where a 'finished product' star can still be very young and marketable for many years.
Ready-made markets in America and Japan
There's a small but significant number of Korean Americans, and Japan has a lot of cultural similarities to Korea allowing works to translate to that market quite well.
For all the product development and clever marketing, the way this video went viral was not necessarily the product of Korean marketing expertise. The kids in South Korea aren't that interested in PSY - he's seen as a washed-up old man! But the video propelled the song to becoming arguably the most successful of this millennium, and that naturally leads to people looking for more in other Korean artists' works.