Well I'm not familiar with Rexec, but if it's a standard x11 program then this should hopefully work.
First you'll need to install X11 on your Mac. I don't think there's a stand alone installer available for download, but you should be able to install it from your Mac OS X Installation disk. Should say something like Optional Extras.
I personally just install the full Xcode developer tools package which installs a bunch of required software for installing software from source code.
Next you'll need to to ssh to the box that will be running the X11 app. Open Terminal (in Application > Utilities) and run the ssh command with the -Y flag (I used -Y instead of -X for security reasons. If this doesn't seem to work you can use ssh -X instead, but it's not recommended. See the man page on ssh.):
ssh -Y username@hostname
Once logged in you can run the app from the command line (if it's in your $PATH):
Hopefully that's all you need to do. You might have better luck doing those two commands from xterm (instead of Terminal). For more information on X11 forwarding from/to a Mac check out Configuring and Running X11 Applications on Mac OS X from Apple's website.