Usually, 'Location' contains a full URL, including http: and the hostname. This is the case outlined by DVK.
Location: /cgi-bin/mycgi.exe/something/
This is actually something else: an internal redirect. It is defined by the CGI specification and works in some other server environments derived from CGI, such as PHP. When Location contains a 'virtual path', Apache serves up the page/script in that path straight away, without the browser knowing there was any kind of redirect.
Obviously that's not what you want as it makes no sense to do a 301 internal redirect when the browser will never see that it's a 301.
Location: something/
This, on the other hand, is nothing. It's not a full URL and it's not a virtual path as it doesn't begin with '/'. Apache doesn't know what to do with it, so it just guesses that it isn't a virtual path so spits it back to the browser with no further comment.
It's invalid to send this in a 'Location' header to a browser, but many of them will allow it anyway, which is why it appears to work. Really you should be passing the full URL:
Location: http://www.example.com/cgi-bin/mycgi.exe/something/