"There are plenty of guidelines out there as to how "fast" a UI ought to be, but how can I measure it?"
This probably goes without saying, but the way to measure UI latency is to take the difference between when an action or event in the UI begins and when it completes. This can be done non-programmatically by manually recording those times, or programmatically by getting a timestamp immediately before you begin some action, then a timestamp immediately after the action completes, then taking their difference. That time difference is the application's UI latency for that action.
Taking these measurements for the set of actions that comprise a UI flow, and doing that for a representative set of UI flows, should give a high-level picture of UI latency in an application.
"Are there any tools available to help measure the UI lag of a given application running on a given computer?"
Yes. Latency in the user interface is the sum of latency in various subsystems throughout a machine: the network, file I/O, CPU, memory, etc. UI latency can be measured at a high level, but can also be measured at a lower level by looking into latency in one of those components.
Below are some specific tools and techniques you can use for measuring and analyzing UI latency in different types of application, either at a high level or a component level.
If you're just looking for rough measurements of UI latency, sitting through a video playback works for you, and you don't need more than a single or a few trials, then I'd first look into a UI flow playback solution like the ones suggested in this answer to your question by Mel and Ben Brocka. The Camtasia option sounds promising for this use case.
If you're looking for precise measurements of UI latency, fast and automatic repeatability in those measurements, and the option to build quick and robust reporting of that UI latency (and you have the time and a technical background/inclination), then an OS-level automation solution might be worth looking into. AutoIt is a popular automation framework for Windows; AppleScript/AppleScript GUI Scripting seems to be the closest equivalent for Mac.
The basic approach with AutoIt or AppleScript would be the same as any other programmatic latency measurement: get a timestamp immediately before you begin some action, then a timestamp immediately after the action completes, and the difference of those two is your UI latency.
Maybe this approach is overkill for your needs, maybe not. The question is fairly broad in scope.
Applications that communicate over a network
Network latency often leads to latency in the user interface. Many applications, whether they're OS-native or built for a browser, send and receive messages using HTTP or some other network protocol.
Wireshark captures all network traffic (including HTTP traffic) going to and from a machine and has features to analyze it. If your application isn't running in a web browser and you'd like to isolate the network's contribution to UI latency, this is probably your best bet for deep analysis.
Charles Proxy and (for Windows) Fiddler are also browser-agnostic tools useful for network latency analysis for HTTP/HTTPS traffic.
Applications that make substantial use of 2D and 3D graphics are obviously popular at the native level, and web browser-based graphics applications are also popular (with Flash dominant but waning, and HTML5 Canvas and WebGL less popular but on the rise). A main measure of UI lag in these applications is frame rate (i.e. frames per second; FPS). Many graphics-heavy applications have features that expose this measurement to the user without needing special tools.
On the web
Web browsers and web sites/applications that run inside them represent a large subset of "a given application running on a given computer".
One of the best tools for measuring latency on the web is a browser's waterfall diagram of network traffic. This is available on Firefox in the Firebug extension's "Net" panel, Chrome and Safari in (Gear icon) -> Tools -> Developer Tools -> Network, and Internet Explorer 9 in (Gear icon) -> F12 developer tools -> Network (Start capturing). This question on Stackoverflow and its answers give a good overview of how to interpret waterfall diagrams for network traffic. Conveniently, at least in Firebug and Chrome, these waterfall diagrams can be exported and saved for later analysis.
The free service at WebPagetest.org is another great way to measure latency -- you can simply enter a URL and get performance results. The tool offers a bunch of great features. Each set of test results get their own URL, so you can link to them or bookmark them. You can also export results in the same format as Chrome and Firebug make available. Perhaps most significantly, you can test page load times from a variety of different browser types, connection speeds, and locations across the globe.
And, if you're the developer of a website or web application, you can also analyze end-to-end UI latency during page transitions with the Navigation Timing API (W3C specification, more documentation, browser support matrix). These latency measurements could be recorded for a wide swath of users and analyzed in aggregate to get a decent overview of performance for all users.
For some aggregate data on page load latency (a type of UI latency) and performance on the web, Steve Souder's HTTP Archive is a good resource.
The tools and resources above are useful for measuring and analyzing latency due to network traffic, and specifically page load times. This is usually the biggest cause of latency in web applications.