That should be it.
Have a static mapping of a public IP address to the private IP address of the Terminal Server. Allow destination TCP port 3389 to Terminal Server machine from clients and allow source traffic from TCP port 3389 back to the clients.
If it is not working you can try these troubleshooting steps:
1. Setup debug on the router to see if the packets are making it through.
2. You can also increase the level of logging detail and sift through the log to see if the packets are still blocked for some reason.
3. From the client machine you can watch run 'netstat -n' continuously to see if you get a TCP connection. If you do then you are connecting to the Terminal Server and it is dropping you for some reason, like perhaps encryption is setup as required on the server but it is not being used on the client.
4. Check the Windows NT/2000 Event log for any errors.
5. Try setting up a test client on the public network if the router if possible and see if it works from there. It is possible your ISP or someone between the client and server is blocking TCP 3389.
Also for anyone who's interested. If you want to use Windows terminal services from a Linux box check out the rdesktop program at
Bluecrack