Does Facebook provide a URL the user can access that will take him to his profile page with the "What's on your mind" box auto completed with a value provided in the URL? I need something like "http://facebook.com?status=This is my new status message".
It appears you'll have to authenticate as described on the REST api documentation for status.set: http://wiki.developers.facebook.com/index.php/Status.set
I couldn't find another option, and since they require you to authenticate for that method, it is reasonable to assume they'll require you to authenticate for any api that lets you update the status.
Try this. It works fine for me.
http://www.facebook.com/share.php?u=<your encoded status here>
Use FB.Connect.streamPublish, like so:
FB.Connect.streamPublish("I just visited dandu's website!");
Of course, this means creating an application and loading the Facebook Connect JS libraries in your website, check their docs for how to do that (setting up can be a daunting task). The advantage of doing so is that you don't need extended permissions. However, the user will be prompted and will have the choice of not updating their status through your app.
AFAIK, there's no simple URL to set a user's status (like twitter has), just the "sharer.php", which doesn't take a status message.