The standard solution is to use use a VPN between two routers, and you adjust the routing so all LAN-to-LAN traffic crosses the VPN.
Domains/Workgroups are really not related at all. A more relevant bit of information would be what type of routers both sites have, and if they can create L2TP, PPTP, or some other encrypted tunnel, or if they are running a standard OS like Linux where you can install software. There are many routers that already support VPN connections. Even some home-routers can do it if you install custom firmware. You can create a VPN between your servers, though getting the routing right may be a bit tricky.
I really like OpenVPN as a solution if I have a system that will support it. Many other good VPN solutions exist.
The obvious solution seems to be VPN,
but can VPN be implemented on the
routers only? Can the computers on the
network be configuration-free?
These completely depends on what type of router you have. If your router is a computer running Linux then yes. If your router is an inexpensive broadband router, then maybe your current hardware can do this. If your current hardware can't do this, you can certainly buy routers that will.
The clients really shouldn't need to know anything about the VPN.