There are a ton of template engines out there, for every different language and platform you can imagine. Some people claim PHP is just a fancy template engine. Others say printf is the first and only real template engine. There are many tools out there that meet various niches and requirements in this fairly broad space. Many templating engines are only available for one or two programming languages/platforms. Without debating the merits of the platforms, here are the criteria for the perfect template engine.
Be output format agnostic
How it looks matters. The templates should be pretty, and the output should be pretty, and the template should look similar to the output. For example, HAML is pretty, and the output is pretty, but the template doesn't look much like the output. Velocity templates look OK, the output looks similar to the template, but the output is ugly, it's darn near impossible to have a nicely indented template and nicely indented output.
The engine has to be fast. It doesn't make much sense for your application to spend a huge percentage of it's time rendering a display. That should be the easy part of your application. I know that CPU and RAM are cheaper than they have ever been, and I believe in horizontal scalability, but I also believe in clean, fast code. XSLT is great at a lot of things, but it is _so_ slow.
Code does not belong in templates
We are talking about a template engine, not a compiler. You should not be able to put "code" in your template. This is one of the things I hate about PHP, JSP and ERB. Even though you shouldn't, you can put any hunk of code you want into your template. PHP is a fairly robust object oriented programming language, but at it's roots, it was a template tool, and I can put any chunk of code I want into my "template". If your template language can handle exceptions, or has the notion of subclassing, then it isn't a template, it's a programming language.
Logic does belong in templates
There is a place in a template engine for making decisions, just not complicated ones. Looping constructs, conditional statements and variable assignment are all perfectly acceptable things to do in a template. Lots of template engines have this right, with just the right number and function of their template commands. ClearSilver, Velocity and Smarty are good examples of the proper scope of implementation.
Allow definition and calling of macros
I am a firm believer in not repeating myself. The template language should let me define macro's or snippets or whatever you want to call your reusable hunks of template. The engine should allow for some kind of include directive, so that my commonly used macros can live in a separate file and be accessed from a number of different templates. JSP tag libraries are exactly the right idea, although perhaps carried a bit far.
Can be processed to an intermediate representation for effeciency purposes
We would call this compiling your template, but that would make people think that you can put code in your template. And that is wrong. But there is nothing wrong with making it fast. Cheetah does this, and so does Smarty. Cheetah's way is better, because processing to an intermediate representation for effeciency purposes (compiling) is a development activity, not a run-time activity. In some languages the interpreter is the compiler (Python and Ruby), but that's no excuse to do something dumb like compiling at run-time. On a related side note, optimizing runtime performance is a worthwhile and encouraged activity (say what you want about Java, but the HotSpot Virtual Machine is dang cool), and yes, I'm aware that these are essentially the same activities.
And don't be backwards. Include != layout. Rails has a very nice layout facility. It essentially let you "include" the changing content, instead of "including" the static content. The genshi method works, but isn't quite as elegant; XML is too verbose to really be elegant.