I think that ATI and NVIDIA each have their own specs for "upgradable" laptop graphics.
Both of these are based off of PCI-Express technology, but I'm pretty certain that each is proprietary.
NVidia's is called "
MXM", ATI's is "
AXIOM".
All of ATI's X series mobility cards (Radeon Mobility
X300,
X600,
X700, and
X800) support AXIOM, however, I don't know if all notebooks with Mobility Xx00 GPUs have AXIOM, or if it's merely an option that the manufacturer can support if they so choose.
Nvidia's Geforce GO6xxx series are most likely the only ones to support MXM (I don't think they extended support to previous versions of their mobile GPUs).
ATI says that AXIOM includes "FlexFit" which basically means that all of the Mobility cards are the same size and thus completely interchangeable. (I don't know, however, if the cooling solution that comes with your Mobility X300 will be robust enough to cool the X800 you upgrade to). I'm pretty certain MXM is similar but I can't find that specifically stated on Nvidia's website.
I don't know what the cheapest notebook is, but it would probably have either a Mobility X300 or a Go6200.