My network topology is a star, with one router/modem + 3 computers.
My computer runs Debian GNU/Linux testing, with Linux 2.6.26 on x86_64.
The other two computers run Microsoft Windows XP, and have low security policies.

I'd like to create a VPN but I need to strongly separate it from my LAN because the two Windows machines would fall immediately to any kind of attack, as they are administered by newbyes.
The ideal solution would allow anyone who connects to the VPN to be in a virtual LAN, but would allow no communication to the windows machines.
I'd also like to allow ssh access to my machine, and I would probably use a key+password authentication, for additional security.

What software to use? What configuration?
OpenVPN seems the right software, but I have no idea on how to configure it to obtain my idea.

Do you actually need a full vpn? Seems like all you'd need to do is have your router port forward the ssh port (22 if you haven't moved it) to your linux box anything extra could be tunneled over the ssh.

yes, the main objective is to create a lan for everyone who connects to my pc [similar to hamachi], and I don't want everyone to have a shell on my pc

If its a mix of *nix and windows then openvpn or tinc are probably your best bet for the vpn. As for the setup you shouldn't need to do anything special with the vpn's to keep them from accessing the internal windows boxes, worst case you just put in an iptables drop for traffic from a vpn address going to the internal windows boxes' addresses

what about NAT, how does tinc/openvpn work behind a nat?

If the server side is behind a nat then you'll need to have your nat/firewall port forward the port the server is listening on. On the client side you might need to have it do a hearbeat or keepalive to keep path open if you are using udp if you are using tcp then the client side should work through nat.

how to setup for "heartbeat" or "keepalive"?
how to choose between using udp or tcp?

UDP tends to be faster since it has less overhead then TCP. TCP tends to work better with firewalls since you have an established stream rather than disjointed packets.

The heartbeat or keepalive will vary for each different vpn. Openvpn's is --ping, you can also use --keepalive which combines --ping and --ping-restart.

thank you for all the info