It was possible to create a WDS between the older 802.11g AirPort Express and the Linksys WRT-54GS and this (as you know) has been documented on the Internet. However, I do not know of anyone that has been successful doing so with either of the 802.11n generations.
The two methods that you have tried would not work as neither is the proper method to set up a WDS. Please check out the following Apple Support article for more details. If you are successful in setting a WDS between them, please post back your results.
1) Creating a new network is if you will have Airport Express connected via ethernet, like a roaming network.
2) You are correct, Joining an existing network will only JOIN the network like a client, to be apart of the network.
The Airport Express can only wireless extend another Airport router, not 3rd party routers (but it's not impossible). You can contact Linksys support to see if the router will allow the network to be extended. Maybe you can consider a router that will be compatible with the Linksys.