It seems like that's the way to do it. As long as you're correctly following the header format.
Here's someone else who asked the same question, more or less.
http://stackoverflow.com/questions/833715/returning-http-status-codes-in-python-cgi
Are you following HTTP specs when you print the status code? Can you try printing just the status code and not its description?
Maybe like...
print '''Status:501
Content-type: text/html
'''
Or it should be like...
print '''HTTP/1.1 501 Not Implemented
Content-type: text/html
'''
Could you test with your setup to verify?
Returning status from CGI:
http://oreilly.com/openbook/cgi/ch03%5F07.html
I guess "Status: 501 Not Implemented" like you had it originally is the way to go. I don't know why it's not working. Are you printing any non-header content before printing the status code?
Yet another source that confirms you're doing it right (look in section 6.3.3.):
http://www.ietf.org/rfc/rfc3875
EDIT 1,2,3: extended answer