What program do you use? I know how to use patterns well in Photoshop. There isn't a specific stage where a pattern should be used; it depends on what you want to do with the image. So use it however, whenever you want.
I most often see them used as layout backgrounds and on banners. I've used them often in avatars and I have easy access to them so I'll just show some examples of what I've made with patterns:

The little swirls and lines you see in white are a pattern I used off of the site you linked. I just used a blend mode other than normal to make it appear faded.
Same as a few others: