The core problem is that RFC 1867, the specification for file uploads over HTTP via the multipart/form-data MIME type, does not provide any method for providing file upload progress.
A file upload is actually just a fancy form submit. CGI scripts, PHP, and all other web technologies that rely on a front-end web server to first accept the request might not actually begin executing until the entire upload has completed. This means that they generally can't even know when the upload has started, only when it's been completed.
New versions of PHP's APC extension include a workaround for this problem that performs some level of black magic that allows it to know about uploads earlier. It only works as part of mod_php, though. The devs don't seem to have plans to support it under FastCGI.
Another server-side option would be the "uploadprogress" PECL extension. I'm not entirely sure what kind of black magic it uses. The source suggests that it actually hooks into the processing of the multipart MIME parts. (This suggests that at least some SAPIs stream form data to PHP as the client uploads it. I know that at least some FastCGI servers buffer the entire request before passing it along, so this might not work for you. YMMV.)
Both of these options are for normal file uploads. Ajax -- or rather, XMLHttpRequest -- does not support file upload operations. Most of the workarounds in this area involve creating an iframe and submitting a form there, and that also implies someone else's client-side work. If you're going to go through that level of hoop jumping, you'd may as well use one of the modern file upload widgets.
Personally, I use Plupload, a Javascript widget that can work with everyone's favorite Javascript library, jQuery. Some others swear by Uploadify. Regardless, both of these widgets offer a high degree of user feedback as to upload progress. They are likely to be easier for you to implement than APC or uploadprogress and have the advantage of being built and tested thoroughly by other people.
Plupload supports multiple upload engines, including HTML5, Gears, Flash, Silverlight, oldschool HTML4 and more. Between HTML5, Flash and Silverlight, you've pretty much just covered 100% of your audience. It also allows you to subscribe to events and have your own code perform magic. For example, if you need server-side file upload progress information, you can have the client regularly send updates to a different script. This would be useful if you regularly have clients uploading huge files and you want to know about it in real time.
tl;dr: Uploading is hard, let's go client-side!