I'm trying to get WDS working between an WRT54GL running OpenWRT, and a Motorola WR850G running stock firmware.
There's lots of info on this page.
The main difficulty I'm having is with the totally different interfaces on the two routers.
According to the openwrt.org forum, you need to run the 2.4 kernel with the proprietary Broadcom drivers. The 2.6 kernel uses the free drivers, but they don't yet do WDS.
Write down the MAC address of the WiFi interfaces for each router. That MAC is not the one on the bottom of the router. (That's the MAC for the WAN port, which the ISP may need.)