Android is an open mobile phone platform that was developed by Google and, later, by the Open Handset Alliance. Google defines Android as a "software stack" for mobile phones.
So, what's a software stack? It's made up of the operating system (the platform on which everything runs), the middleware (the programming that allows applications to talk to a network and to one another), and the applications (the actual programs that the phones will run). In short, the Android software stack is all the software that will make an Android phone an Android phone.
Android is based on the Linux operating system, and all of its applications will be written using Java. Google says Android will "ship with a set of core applications including an email client, SMS program, calendar, maps, browser, contacts," and more.
Anyone can download an Android software development kit from Google and write an application for Android.