Language
Different programming languages will have their own flavour of bugs.
In C, adding debug statements can make the problem impossible to duplicate because the debug statement itself shifts pointers (far enough to avoid a SEGFAULT). Pointer issues are a nightmare to track and replicate, but there are debuggers (such as GDB and DDD) that can help.
In Java, an application that has multiple threads might only show its bugs with a very specific timing or sequence of events.
Environment
Is it a server-based web application? Is it a desktop application? Is it browser-based? Does it only happen in production?
Depending on the complexity of the environment in which the application (that has the bug) is running, the only recourse might be to simplify the environment.
Exit extraneous applications and kill background tasks.
Variables and Consistency
Eliminate as many unknowns as possible. Isolate architectural components. Simplify by removing non-essential, or possibly problematic (conflicting), elements. Deactivate different application modules.
Remove all differences between production, test, and development. Use the same hardware. Follow the exact same steps, perfectly, to setup the computers. Consistency is key.
Logging
Logging is an invaluable tool. With it you can correlate the time events happened. You can examine logs for any obvious errors.
Hardware
If all the software pieces appear fine, consider that hardware is a possible source of the issue. Are the network connections solid? Do the harddrives have bad blocks? Are the CPU fans whirring away? Does the motherboard have enough power for all components (CPU, network card, video card, drives)?
What happens when you run the application locally (i.e., not across the network)? Are other servers experiencing the same issues? Is the database remote? Can you use a local database?
Time and Statistics
When does the problem happen? How frequently? What other systems are running at that time? Gather hard numerical data on the problem. A problem that might, at first, appear random, might actually have a pattern.
Change Management
When did the problem first start? What changed in the environment (hardware and software)? What happens when you roll back to a previous version? What are the differences between the version that has problems and the version that does not?
Library (Mis)management
Windows has DLL Hell: conflicting versions of DLLs littered throughout the system.
Unix has libraries sprinkled throughout directories, shot with broken symbolic links.
Perform a fresh install of the operating system, and include only the supporting software required for your application.
Java library files can be equally evil. Make sure every library is only being used once. Sometimes the application container will have a different version of a library than the application itself. This might not be possible to replicate in your development environment. Use a library management tool such as Maven or Ivy.
Sleep
It is worth reiterating what others have mentioned: sleep on it. Spend time away from the problem, finish other tasks (like documentation). Be physically distant from computers and get some exercise.
Bug Characteristics and Testing
Code a detection method that triggers a notification (e.g., log, e-mail, pop-up, pager beep) when the bug happens. Use automated testing to submit data into the application. Use random data and use data that covers known and possible edge cases. Eventually the bug should reappear.