The next TKL release will be based on Ubuntu Lucid/10.04 which includes MySQL Server 5.1 in the repositories (see full package details here). I suggest that you hold out for now if you can, especially as TKLBAM will make migration a snap. There is no clear timeframe for release though (just as soon as they can) so if you urgently need 5.1 then you may need consider installing via an alternative method.

Off the top of my head, choices you have are (in the order I'd possibly consider them):

1. Build your own appliance based on TKL-Core-Lucid beta (beta of Core for new TKL release). IMO this is probably the best option if you need to upgrade. Will require some Linux knowledge (or willingness to aquire it).
2. Use Basil's LAMP TKLPatch (which as the name suggests, also includes Apache & php). The easiest method while avoiding some of the pitfalls of method 3. Although is possibly overkill (unless of course you want a full LAMP stack). May also require some tweaking (as it is set up as a LAMP stack rather than MySQL only).
3. Find an alternative repository such as a PPA or somewhere else - easy but not recommended as it may raise security and/or stability issues (do you know what backdoors and/or unsuitable optimisations the compiler may have added to the code?). Also it may also raise issues down the track if/when you want to migate to the new offical TKL MySQL release (due to mismatched MySQL versions or other issues).
4. Install tarball, rpm or build from source (downloaded direct from MySQL site) - Not for the faint of heart, can be quite technical and/or problematic. Quite possible you will encounter issues. May also lead to issues down the track if/when you want to migate to the new offical TKL MySQL release (as in 3). Would be preferable to option 3 if you can find a good tutorial online.

If you can't wait and wish to press ahead with one of these methods then I can probably give you a few more pointers.