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".
Answer
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.