With a testing framework, you won't waste time rolling your own. For Java, you could start with JUnit.
TDD is a formalized approach to writing test functions as you work, which you already do, while simultaneously designing your code. There are many sources on it around the internet, but Kent Beck's book took the magic out of it (a good thing) for me:
Of course, there are many other specific techniques you can use to test that your algorithms do the right thing, all dependent on what you've made. Regardless, I try to make sure that the a real user gets their hands on an up to date build as often as possible, and they're sure to show me all of the ways that my software is technically excellent, yet in no way solves their actual problem.
Since I'm a Rubyist, I use Cucumber and RSpec to do testing. http://cukes.info http://rspec.info (note that you can use cucumber to test any language, and I bet you could use JRuby to test java.
Here's the original work on the subject, by Dan North: http://blog.dannorth.net/introducing-bdd/
A little Rails specific, but this post by Sarah Mei is pretty awesome: http://www.sarahmei.com/blog/2010/05/29/outside-in-bdd/
These two Railscasts on Cucumber are good: http://railscasts.com/episodes/155-beginning-with-cucumber http://railscasts.com/episodes/159-more-on-cucumber
But really, conceptually, BDD isn't that complicated. The hardest bit is figuring out the tooling for whatever language you're using, getting comfortable with it, and practicing. I know the Ruby side of this well, but if you're using another language, I'm not sure I can be of much help.
Your links to the RailsCasts screencasts are great also. PeepCode also has their Cucumber Screencast that is a little more detailed than RailsCasts.
These are all Ruby or Rails specific. Cucumber itself is a DSL to be used along with another language, and there are projects underway to implement Cucumber or Cucumber-like frameworks for other languages like Python, Java and .NET