Templates are not something I generally recommend because there are a number of potential pitfalls that are all-to-easily fallen into. However, in order to make your life easier, I've put together a short list of the hints and tips I've learnt the hard way over the years so that you can learn from them:
Start small, and work your way up. If you try to put together a list of all the different things you want to do at the beginning, you're likely to make the system more complex. Instead, think of the most important four or five template objects, then do the rest as you encounter a need for them.
Using str_replace() for templates can be optimised by passing in the parameters as arrays.
Use a code caching system or you'll regret it - templates are notoriously slow devices, and it's cheaper to get a decent code cache than it is to just buy more servers.
Don't be afraid to split up your system into multiple smaller files for easier manageability; template systems have a tendency to get more complex with each code update, and anything that helps is a good thing.
The best template systems I've seen have been object-oriented - it's an entirely personal decision how you code yours, but do consider OO first.
If you can statically cache pages, do so. This makes for a big performance boost.
Although it's possible to run complex regular expressions for your template interpretation, it causes a real speed hit: evaluate each one carefully.