When you want to ask for directions on the street in Korea, it is best to start with 실례합니다 'Excuse me', a polite way to seek someone's attention. People on the street will expect this expression to be followed by an inquiry concerning directions, and hence will be ready for it. 말씀 좀 묻겠습니다 (lit. 'I will ask you something') can immediately follow 실례합니다.

(1) A: 저, 실례합니다. 말씀 좀 묻겠습니다.
 B: 네.
 A: 이 근처에 우체국이 어디 있어요?
 B: 은행 옆에 있어요.

(Note: 저... is used at the beginning of conversation to get the other person's attention, and also for hesitation.)

When you want to get more specific directions, you may ask 어떻게 가요? For instance,
 
(2) A: 여기서 어떻게 가요? 'How do I go from here?'
 B: 이 길로 쭉 가세요.      'Go straight.'
    그럼 오른쪽에 있어요.    'Then it is on your right side.'
 A: 감사합니다.

(으)로 가세요 'Go toward the direction of...' is often used to give directions. More expressions about direction:
 

[연습 1] (Pair work) Ask and give directions for each location on the basis of dialogues (1) and (2) above.

(1) 은행
(2) 책방
(3) 극장
(4) 약국
(5) 다방