How to tweet using terminal?

This error message is because Twitter needs OAuth for authentication. Take a look at TTYtter if you don't mind a Perl app:

Noooo, not another Twitter client! Yes, another Twitter client. The difference here is that you're dealing with a multi-functional, fully 100% text, Perl command line client.

• In interactive mode, it is a fully interactive client with asynchronous background updates and commands. Use it over telnet, ssh or even a dummy terminal. Supports Streaming API, ANSI colour, UTF-8, hashtags and Twitter Search!
• Works within your favourite environment: use a compatible readline library (like our own bespoke Term::ReadLine::TTYtter), or modify prompt and input methods for many popular window and session managers. Or don't: basic editing and screen management features built-in.
• From the command line, use it to update your Twitter in shell scripts, from cron, and so on.
• Security: Supports Twitter OAuth and HTTP Basic Authentication, and SSL where supported by your user agent.
• Notification support with Growl and libnotify (and extendable to others via the API).
• Geolocation support: hand your GPS coordinates to TTYtter for any application.
• Lists support, including fast creation and modification, and merging lists with your timeline as "custom timelines."
• Supports Twitter-alike APIs such as StatusNet and Identi.ca.
• Supports standard timelines and automatically fetches direct messages, and optionally replies/mentions, and runs queries against the Search API and incorporates them into your timeline as well.
• New and old re-tweet support.
• Write and use your own custom extensions!
• Run detached in -daemon mode, and make your own Twitter bot!

TTYtter has been deprecated. Development now continues in the fork, oysttyer.

Try T. Very powerful, easy to use and written in Ruby.

For example, you can tweet directly from the terminal, by executing:

t update "I'm tweeting from the command line."

2016 Update

There is a project called Twurl - an OAuth-enabled curl for the Twitter API:

Twurl is like curl, but tailored specifically for the Twitter API. It knows how to grant an access token to a client application for a specified user and then sign all requests with that access token.

It also provides other development and debugging conveniences such as defining aliases for common requests, as well as support for multiple access tokens to easily switch between different client applications and Twitter accounts.

Instead of this from the question:

curl -d status="Your Message Here" https://twitter.com/statuses/update.xml

you use something like this:

twurl -d status="Your Message Here" /1.1/statuses/update.json

after you authorize yourself first as explained in the readme.

(note that you don't have to use the protocol and hostname in the URL as you would with curl)

This program was originally written by Marcel Molina who worked at Twitter at that time and it is now an official Twitter project on GitHub.

Many people are asking specifically how to use curl to use the Twitter API and twurl is probably the closest to curl as you can get today.