1) No, most wireless routers also have wired ports, just like your regular router, so you can hook them up via the regular ethernet cables. Unless you want your PCs to be wireless too, in which case, yes you will need to get a wireless card for each PC.
2) Well, you want to get the latest versions, but what is really important is that the router broadcasts over 802.11b or 802.11g standards. This will usually be in the router tech specs on the box or manual, or the online product spec.
3) Do you have two separate DSL lines? If so, you're really wasting your money, unless the PCs are really far apart. You just need one DSL modem -> one router -> Multiple PCs/Wii/etc. In any case, you would be hooking your router up to just one of the modems, and there shouldn't be any problems. And no, there are usually no compatibility issues between PCs and routers.
4) An 802.11g router is your best bet, but make sure you can return the product if it doesn't work out for you.