I live in a two-story pre-war apartment with very thick walls and
floors. My cable modem is on the second floor, and I have an 802.11b
Linksys wireless router that doesn't cover most of my first floor. 
Question: will an 802.11g router improve coverage or do I need to try
something else.  If it's something else, what is the best alternative
(powerline, repeaters, directional antennas?)

Try using an 802.11 range extender. I have recommended it to a client
I have dealt with and solved his similar problem.
http://www.linksys.com/products/product.asp?grid=33&scid=38&prid=629

Its realitive cheap. About same cost as a Wireless NIC. Several places
sale it. CDW and MWave.com have it.
Good Luck
-Torpedo

torpedo is right, some sort of repeater is what you need.

try to work angles around your walls, so the repeater or a series of
repeaters has a clear line to of site to each device.

dear Sir,
         As you already have a linksys 802.11b wireless router, my
recommendation is to buy a Netgear WGXB102 wireless kit. It is a combo
of two Powerline products. One is a XE102 and WGX102 802.11g Wireless
Access Point which can also be used a wireless access point/router.
You can continue to use the linksys 802.11b wireless router as your
main router, Use the Netgear WGX102 as a access point. Connect the
XE102 with the linksys router using a ethernet cable and connect the
xe102 to power socket. Go to first floor and connect the WGX102 with
power socket on the first floor and it will give you good signal
strength. I would also recommend you to buy a WG511 wireless card for
the laptop and it has a backward compatibility with 802.11b wireless
networks. Make sure that you should have a same power socket
throughout your home.

This will the most cost effective and custom built solution for your problem.

Regards

Click this link to view the features of WGXB102
http://www.netgear.com/products/details/WGXB102.php

Well, I dont know if the new one would work or not, considering i
never tried it in your place, but you could always MAke your own
antenna, i know it might sound goofy, but if you got skills you could
use an old Radiater, as an antenna, and it will actually work
extremely well, if you do it right.

http://www.e3.com.au/modules.php?op=modload&name=News&file=article&sid=568
That link as details!! check it out.

fyi I wound up solving the problem by buying the Belkin pre-N product.
 I am aware that people are skeptical because the standard isn't
"certified" yet, but it works really well and was a snap to set up.  I
was concerned about the powerline solution because the wiring in the
apartment is very old, and I wasn't very sure if the wiring was
consistent.