I work in computational science, and as a result, I spend a non-trivial amount of my time trying to increase the scientific throughput of many codes, as well as understanding the efficiency of these codes.

Let's assume I have evaluated the performance vs. readability/reusability/maintainability tradeoff of the software I am working on, and I have decided that it's time to go for performance.  Let's also assume that I know I don't have a better algorithm for my problem (in terms of flop/s and memory bandwidth).  You can also assume my code base is in a low-level language like C, C++, or Fortran.  Finally, let's assume that there is no parallelism to be had in the code, or that we're only interested in performance on a single core.

What are the most important things to try first?  How do I know how much performance I can get?  

First of all, as skillman and Dan have pointed out, profiling is essential. I personally use Intel's VTune Amplifier on Linux as it gives me a very fine-grained overview of where time was spent doing what.

If you're not going to change the algorithm (i.e. if there will be no major changes that will turn all your optimizations obsolete), then I'd suggest looking for some common implementation details that can make a big difference:


Memory locality: is data that is read/used together also stored together, or are you picking up bits and pieces here and there?
Memory alignment: are your doubles actually aligned to 4 bytes? How did you pack your structs? To be pedantic, use posix_memalign instead of malloc.
Cache efficiency: Locality takes care of most cache efficiency issues, but if you have some small data structures that you read/write often, it helps if they are an integer multiple or fraction of a cache line (usually 64 bytes). It also helps if your data is aligned to the size of a cache line. This can drastically reduce the number of reads necessary to load a piece of data.
Vectorization: No, don't go mental with hand-coded assembler. gcc offers vector types that get translated to SSE/AltiVec/whatever instructions automagically. 
Instruction-Level Parallelism: The bastard son of vectorization. If some often-repeated computation does not vectorize well, you can try accumulating input values and computing several values at once. It's kind of like loop unrolling. What you're exploiting here is that your CPU will usually have more than one floating-point unit per core.
Arithmetic precision: Do you really need double-precision arithmetic in everything you do? E.g. if you're computing a correction in a Newton iteration, you usually don't need all the digits you're computing. For a more in-depth discussion, see this paper.


Some of these tricks are used in the daxpy_cvec this thread. Having said that, if you're using Fortran (not a low-level language in my books), you will have very little control over most of these "tricks".

If you're running on some dedicated hardware, e.g. a cluster you use for all your production runs, you may also want to read-up on the specifics of the CPUs used. Not that you should write stuff in assembler directly for that architecture, but it might inspire you to find some other optimizations that you may have missed. Knowing about a feature is a necessary first step to writing code that can exploit it.

Update

It's been a while since I wrote this and I hadn't noticed that it had become such a popular answer. For this reason, I'd like to add one important point:


Talk to your local Computer Scientist: Wouldn't it be cool if there were a discipline which dealt exclusively with making algorithms and/or computations more efficient/elegant/parallel, and we could all go ask them for advice? Well, good news, that discipline exists: Computer Science. Chances are, your institution even has a whole department dedicated to it. Talk to these guys.


I'm sure to a number of non-Computer Scientists this will bring back memories of frustrating discussions with said discipline that led to nothing, or memories of other people's anecdotes thereof. Don't be discouraged. Interdisciplinary collaboration is a tricky thing, and it takes a bit of work, but the rewards can be massive.

In my experience, as a Computer Scientist (CS), the trick is in getting both the expectations and the communication right.

Expectation-wise, a CS will only help you if he/she thinks your problem is interesting. This pretty much excludes trying to optimize/vectorize/parallelize a piece of code you've written, but not really commented, for a problem they don't understand. CSs are usually more interested in the underlying problem, e.g. the algorithms used to solve it. Don't give them your solution, give them your problem.

Also, be prepared for the CS to say "this problem has already been solved", and just give you a reference to a paper. A word of advice: Read that paper and, if it really does apply to your problem, implement whatever algorithm it suggests. This is not a CS being smug, it's a CS that just helped you. Don't be offended, remember: If the problem is not computationally interesting, i.e. it has already been solved and the solution shown to be optimal, they won't work on it, much less code it up for you.

Communication-wise, remember that most CSs are not experts in your field, and explain the problem in terms of what you are doing, as opposed to how and why. We usually really don't care about the why, and the how is, well, what we do best.

For example, I'm currently working with a bunch of Computational Cosmologists on writing a better version of their simulation code, based on SPH and Multipoles. It took about three meetings to stop talking in terms of dark matter and galaxy haloes (huh?) and to drill down to the core of the computation, i.e. that they need to find all the neighbours within a given radius of each particle, compute some quantity over them, and then run over all said neighbours again and apply that quantity in some other computation. Then move the particles, or at least some of them, and do it all again. You see, while the former may be incredibly interesting (it is!), the latter is what I need to understand to start thinking about algorithms.

But I'm diverging from the main point: If you're really interested in making your computation fast, and you're not a Computer Scientist yourself, go talk to one.
