Если речь идет о поисковом продвижении, то идеально сделать субдомен (например spb.domen.ru или ekb.domen.ru) и на нем развернуть копию сайта, с уникальными текстами и контактными данные для этого региона. Если такой возможности нет, то вебмастере укажите дополнительный регион, а на странице контактов обязательно выведите телефон, адрес и почту, относящуюся к региону, где хотите продвигаться. Тягаться с запросами, по которым активно крутятся сайты, из этого региона не получится, но в низкочастотных запросах вылезете точно
Поддоменами или директориями. В Яндексе очень хорошая гео-локация, поэтому в регионах на первые места выходят местные региональные площадки. Самое важное - купите юридические адреса и номер 8800, чтобы привязать поддомен или директорию к Справочнику, иначе все зря.
Точно так же, как и в своем. Например, запустите таргетированную рекламу по нужным сегментам аудитории - к примеру, в Фэйсбуке можно выставить показы рекламы на тех, кто живет или бывает в определенных геолокациях. Кроме того, эффективный канал - контекстная реклама. Вы можете запустить рекламу своего сайта в Яндекс.Директе и настроить показы по определенному региону.