A Doctype, or Document Type Declaration associates the document with a Document Type Definition.
The Document Type Definition is a standard for an XML document. There are many DTDs, for both XML and XHTML documents. XML itself doesn't have much of a schema or a very specific set of rules, apart from the requirement that everything be well-formed. You can think of a DTD as a more specific schema for the document.
Rendering Modes
Due to the standards movement, most modern browsers actually have different rendering modes (standards mode, for rendering your document and css according to more recent web standards, and quirks mode, wherein the browser brings back some rendering ideas from the early days of the web). These modes are instituted for purposes of backward-compatibility. The vast landscape of web pages which were created in the first era of the web are rendered according to the rules of their time, while newer documents can appeal to the new wave of standards. As time goes on and new formats are imagined, a corresponding DTD could potentially be created.
Browser Discrepancies
In an ideal world, a page that is being loaded by a browser would read the Doctype at the top and use it to look up a Document Type Definition. It would then use the schema of that DTD as the basis for reading the rest of the document. Doctypes, then, would be essential for validating markup documents. The DTD would provide the standard against which your document is to be validated.
Unfortunately, it's not an ideal world. Browsers don't necessarily behave consistently here, and if they do, the consistent behavior isn't quite in line with the original vision for Doctypes. Although parsing is done independently of the Doctype, major browsers will at least examine the Doctype to determine the rendering mode. If your Doctype is absent or is incomplete, the browser will likely be rendering in quirks mode. For well-written, modern documents to appear correctly, the browser should be rendering in standards mode. Mozilla, Safari, and some recent versions of Opera actually implement an Almost Standards mode, which is dedicated entirely to transitional pages.
When you change the Doctype and notice changes in the way a page is displayed, it is because the browser may be applying a slightly different set of rules when it tries to parse the document. As a consequence, the resulting page may be a little bit different, depending on whether all of its parts conform to the DTD, or at least, depending on the browser, that your data validates within the rendering mode that the doctype suggests.
Choosing a Doctype
In pursuit of standards-compliance, strict Doctypes should be used whenever possible.
When writing in XHTML, this Doctype is common:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
When writing in HTML 4.1, this one is common instead:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
Some other common doctypes for XHTML and HTML 4 are listed here, for completeness:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Frameset//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-frameset.dtd">
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
"http://www.w3.org/TR/html4/strict.dtd">
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Frameset//EN"
"http://www.w3.org/TR/html4/frameset.dtd">
Debate on Strict versus Transitional Doctypes
Standards evangelists have called for web developers to stop using the Transitional Doctype on new pages and instead use Strict. Again, this is a case where the theory and the practice have some difficulties being reconciled. The original hope of the transitional Doctype was to provide a halfway house for transitioning legacy websites toward standards-compliance. With transitional doctypes, the restriction on elements and attributes is literally "less strict", so developers would be able to get their work running under standards mode sooner, and phase out the outstanding differences over time.
Controversy exists because it isn't always quite so simple for a developer change the Doctype in an enterprise environment. Freelance developers and makers of small- or medium- sized websites may often have an easier time determining their Doctype and making this transition. In an enterprise production environment for a highly-demanded web-based service, there are inherently more complicated dependencies on legacy systems and 3rd party code products, which themselves may be on a roadmap for removal or redesign, but the execution of such changes must be done methodically and incrementally.
Helpful Tools
The W3C (World Wide Web Consortium) is a group which plays an active role in defining these kinds of standards. They maintain a helpful online tool at http://validator.w3.org/ for verifying and validating documents against their standards. There are many other 3rd party tools and browser extensions with similar functionality.