A maneira mais fácil de fazer isso é usar o OpenVPN. Está bem documentado, estoque no linux e disponível no Windows.
Uma VPN é como um tesseract. "dobra" uma rede para que dois sistemas sejam exibidos um ao lado do outro na rede.
Digamos que você tenha um Windows Box A, que se conecta ao roteador 1, que se conecta à Internet, que se conecta ao roteador 2, que se conecta ao servidor Linux B. A VPN cria um túnel para que Box A e Box B sejam na mesma sub-rede.
[Box A] <-> [Router 1] <-> {Internet} <-> [Router 2] <-> [Box B]
Through magical VPN folding becomes:
[Box A] <----------------------------------------------> [Box B]
Sugiro ler o link como ponto de partida. Abrange a configuração do Windows como um cliente e no modo peer to peer, além de ter instruções para o Linux genérico no modo peer to peer. Se você sabe como configurar o Samba, então deve ser trivial adicionar sua sub-rede VPN às redes permitidas.