If you deploy on Ubuntu, and therefore use a .deb package, then your job is easy since you just have to require qt as a dependency and apt will automatically install it as needed.
Windows and Mac however do not have any "good" software management layer, so you have no choice but include the required Qt DLLs with your binary or compile a static one. On Windows you just have to make sure the DLLs are in the same directory as your program. Mac however requires some relinking to be done. This is a big pain, but fortunately Qt comes with a tool named macdeployqt
which does this for you.
So according to my experience, Linux is the easiest platform to deploy to, followed by Windows, and Mac is a good last.
The link to the Qt deployment doc given above is a good starting point. If you need an example, I have written a couple of scripts to build the Windows and Mac binaries of a program of mine. You can have a look at these to get started.
Windows installer:
http://gitorious.org/tagaini-jisho/tagaini-jisho/blobs/HEAD/scripts/buildwin32releases.sh
http://gitorious.org/tagaini-jisho/tagaini-jisho/blobs/HEAD/tagainijisho.nsi
Mac bundle:
http://gitorious.org/tagaini-jisho/tagaini-jisho/blobs/HEAD/scripts/buildosxreleases.sh