Best bet is KAL Airport Limousine (actually, it's a bus).Instructions for people staying in New Seoul:
Tickets are W12,000. You can buy them in the arrivals hall (just before the exits) or on the bus. Bus is cash only.
Stop 4B or 11A (depending on your arrival airline) http://www.airport.or.kr/Eng/transportation/bus.jsp
Use the same KAL Airport Limousine (#1). The first stop is Koreana Hotel. Best Western is just across the street (but don't try to cross ;-)).
Alexey