Вопрос: как сделать подобное на, скажем, вконтакте?
Точно так же. Только нужно будет новое окошко со стилистикой Вконтакте.

Я так понимаю заменой фрейма не обойдёшься, так откуда же подгружается интерфейс?
Оттуда же. Делаешь фрейм на все окно, и интерфейс подгружается с настоящего сайта. Так же как и на сабжевом сайте.