Qt Quick vs. Qt Widget
As someone who develops qt applications professionally, I will choose qml over widgets any day.
Widgets are good for the very basic stuff, but I once you need to create something that is a bit more fancy, widgets will fall short very soon.
Qml is simply way more flexible, you can anchor items wherever you want instead of using the limited layout system of widgets. There are almost no platform-dependency flaws while widgets are full of these. And the property binding system makes it so damn easy to keep your ui in sync with your model.
Note: Qt Widgets have been replaced with QML Widgets; this answer responds to the question as asked, which is now strictly a historical question about the old Qt Widgets.
Qt Quick is a declarative, smartphone-style user interface with support for a lot of the cool animation transitions that are common in smartphone apps. Quick is also a good choice for rapidly developing a prototype. Qt Widget is the traditional desktop-oriented UI model.
Right now (pre-Qt5), Qt Quick support for desktop system features is lacking (but improving). There's not as much support for menus, toolbars, dialogs, and other standard desktop behaviors in Quick, while Widget supports those elements extremely well.
Do you want your app to look and feel native on desktop and tablet platforms, or are you building a simple application around your own custom UI widget? As Mat said, if Qt Quick supports the features you want, that will probably be your fastest approach. If you want to build full-featured desktop versions, Qt Widget is probably your best bet.
Note: In this answer, "Qt Widgets" refers to a Qt Widgets Application, selectable when creating a new Qt application.
This is seven years after the question was first posted... but here's my "objective" two cents to neutralise any developments since then.
A Refresher
Language
Qt Quick projects use QML and JavaScript. The latter carries the brunt of program logic: event actions (Component.onCompleted, onClicked, etc.), math, etc.
Qt Widgets projects use C++ code. (PyQt and PySide, Python bindings for Qt, uses Python.)
Performance and Coding
As such, Qt Widgets could be considered low-level compared to Qt Quick. But this implies that in the long run, a Qt Widgets project will run faster and have better performance. Being low-level can be good though, as Qt Widgets is more exposed to native API (the QtCore module, Qt Style Sheets, etc). That said, it is often used for desktop development.
Qt Quick caters more to mobile development (although it can still be used in desktop development). It has ready-to-use popups, animations, tabs and layouts, flickables, drawers, and the usual controls; all ubiquitous in mobile development.
UI Design
Both have ui files which work with QtDesigner, providing a high-level view for setting layouts and creating interfaces. (In Qt Quick, extensions are .ui.qml. In Qt Widgets, they are .ui.) It's not necessary to use .ui files; you can still choose to programmatically design your UI using QML/JS or C++/Python.
Learning
If you're completely new to programming, I suggest having a look at Qt Quick first. Personally, I think Qt Quick has a gentler learning curve and is easier to work with to accomplish myriads of projects. It's called "Qt Quick" for a reason. (Don't look down on Qt Widgets though, they have some nice modules that outdo QtQuick.)
However, if you've been programming with C++ or Python before, I would suggest taking a look at Qt Widgets first, to get used to their signals and slot mechanism and modules that might interest you (e.g. sql, network, gui) alongside programming designs (e.g. model/view programming for displaying data).
Especially with C++, most non-Qt libraries that do event-handling use while-loops, this is not the case with Qt. They use signals and slots.
In the end, even if you're mainly using Qt Widgets, you might want to look at Qt Quick as it offers a high-level declarative language to work with and allows you to set things up more quickly. (Especially for mobile development.)
Qt provides examples in abundance for both Qt Quick and Qt Widget projects, along with a forum. You shouldn't worry about getting help in the long run. (Don't forget StackOverflow!)
Qt Quick + Qt Widget
So far we've been treating them like separate entities. But it is possible to integrate QML into C++. This allows you to take advantage of Qt Widget, C++, and other modules. For example, QtQuick provides a TreeView but not a TreeModel, which can/should be registered into QML from C++. Often there is a separation of concerns pitch, where Qt recommends separating programs into UI and logic into QML and C++ respectively.
This also comes in handy, if say, you need a backend for intense SQL queries, algorithms, or asynchronous http/xml requests. Isn't that cool? QML/JS frontend plus a C++ backend. Fullstack Qt'er. :-)
(What I haven't tried, is having a Python backend. I haven't touched PyQt yet...)
Firstly, I think you should start with Widget. Widget UI help to learn qt easily additionally if your previous expriences are about front-end things you would learn Quick easily.