When you look at the javadoc of the java.util.Date class, most of the methods are deprecated. Why was this done?
Well, for two related reasons. It was a very poor implementation of the concept of Dates and Times and it was replaced by the Calendar
class.
The Calendar
class, although an improvement, leaves a lot to be desired as well, so for serious Date/Time work, everyone recommends JodaTime. In Java 7 there will likely be a replacement API for Calendar as well, currently called JSR-310.
Edit: In response to the specific question of why the implementation is poor, there are many reasons. The JavaDoc sums it up as follows:
Unfortunately, the API for these functions was not amenable to internationalization.
In addition to this general deficiency (which covers issues like the lack of a Time Zone component as well as the date formatting which is better handled in DateFormat and the inability to have a non-Gregorian calendar representation), there are specific issues which really hurt the Date class, including the fact that year is presented in an offset of 1900 from Common Era year.
Calendar has its own problems, but even as early as JDK 1.1 it was obvious that java.util.Date was not going to cut it. Even though Calendar is arguable the worst JDK API, it has taken until version 7 to attempt to address it.
They're deprecated because Date was written as fast as possible back in the day when they wanted to rush the JDK out the door.
It turns out the Dates and Calendars are Hard. So, they created the Calendar class, which much more thought, in order to handle the Hard Parts of working with calendars.
They deprecated the Date methods and delegated to Calendar because they didn't want to change the behavior of the existing Date methods, and possibly break existing applications.