What is the difference between Debian and Ubuntu?

Yes, there are more fundamental differences. Debian focuses stability and they don't have a for-profit company behind them; Ubuntu focuses ease of use ("Linux for Human beings") in detriment of some conservative stability and has a for-profit company behind them (Canonical).

Of course, there are some other differences (from philosophical ones to release schedules). Check official docs about Ubuntu Development and Ubuntu for Debian Developers to understand them:

Ubuntu is based on Debian, sharing many of its packages, tools and techniques with that project. Differences between Ubuntu and Debian are described in UbuntuForDebianDevelopers.

Ubuntu is periodically released according to a set schedule.

Ubuntu, like Debian, is a free software project which is open to anyone to participate. However, it differs from Debian in that many key project resources, including servers, bandwidth and a number of core developers, are provided by Canonical. Canonical is a for-profit company which derives revenue primarily from services related to Ubuntu, such as support contracts.

Some personal thoughts:

Some people don't like to use a distro that isn't completely run by individuals without commercial interests, so they choose Debian. Users who want a more hand-crafted system usually prefer Debian too since they can create a "base system" and just add what they need, keeping a clean OS.

Other people prefer more ease of use (an out-of-the-box solution that just works), with features that aren't extensively tested but are good enough for daily usage, and choose Ubuntu.

If you don't have philosophical reasons to choose a distro (like free software), I recommend you to download both and just test them to see which one is better. (I use both, for different needs and scenarios.)

Whew, I really think these answers are missing some important points.

DEBIAN HAS A VERY SLOW RELEASE CYCLE. Debian 7 is out now (2013) and Debian has been around since 1996! The general philosophy behind a slow release cycle is the promise that when each release finally comes out, EVERYTHING in that release works. Specifically, all the kernel modules work, all the sources work and there are no issues when the user installs packages. The hope is that the system will work without issues until (at least) the next release comes out, which is generally a year or more into the future. Debian also offers repos that contain newer packages for the interim period (to different degrees, there are "testing" repos, and "unstable" repos, for example), but the user is to install packages from those repos at his own risk, they are not fully supported, or in other words, have not been adequately tested to be considered stable by Debian standards. The hope behind this very conservative development philosophy is that it creates rock-solid systems, so that if someone wants to set up a business on a linux server, they can set up their software once, and it will run without issues or need for any updates for a long time. For the most part, this philosophy works.

Ubuntu has a release cycle that is at least twice as fast as Debian. At the time of writing this, Ubuntu is approaching release 19, with their first release (as far as I know) appearing less than ten years ago. Because these releases are backed by a for profit company, (in other words they have people who make money in maintaining their software) they are able to do more work to test new developments, and can put out stable releases at a much faster rate. Ubuntu is NOT, however, necessarily the best software if your goal is to get the latest updates for absolutely everything you install in Linux. It IS a good option if you want a working system that's easy to use, and in my opinion, the only real option if you are an absolute beginner at linux and want to enjoy using linux (there are other distros oriented toward beginners, so this is just my opinion).

If your goal is to have the latest packages, I would pick a distro that has a rolling release cycle, like Archlinux or Gentoo.

Ubuntu is based on Debian, it uses the same package structure but includes some more upto date versions (Debian is very conservative).

It also has more non-free apps available (Debian is very pro-free)

It also has a very nice isntaller

GmonC and mgb said most of the stuff but i have to add that there are some differences in packages so ubuntu packages are not compatible with debian and vice versa. Of course in theory this works but in practice it's not a good option (im reffering to packages from official repositiories). You can mix single packages but not many of them (believe me, im telling you this from personal exp). Single packages like "gtk2-engines-murrine" will work but something like "lives" could mess up your sys.
Have in mind that there are 4 branches of packages in Debian (stable, testing, unstable and experimental) and in ubuntu you got several too (stable, backports ppa...).