I wanted to do this about a year ago. I tried many different things that I found in forums and such. It was all too much of a pain so I just gave up.
About 5 minutes ago I was getting ready to go to sleep and had a "eureka!!" moment and thought "no, it can't be that simple."
Apparently it is.
Here's what I did:
created a shortcut the normal way. (right-click)
Then opened notepad++ and dragged that new shortcut into notepad ++ and dropped it.
It displayed a bunch of gibberish, but there in the middle was the path to my exe in plain text. "E:\programs\firefoxportable\firefoxportable.exe"
I simply typed a relative path over it. ".\programs\firefoxportable\firefoxportable.exe", (replaced 'E:\" with ".\" and clicked save.
So far it seems to work just fine. I'm using XP pro. Apparently it has no problem recognizing relative paths but the program that creates them when you right click and select "create shortcut" just won't allow it.
EDIT:
Tried this on a different PC at school and it doesn't work.