I am aware that the original poster wants to use Linux and may be talked into using Windows but probably not into buying a Mac. But since other people will have the same question and some of them may be Mac users, here it goes:
Many responders have already suggested creating ingenious folder structures that will help you keep a basic level of organization to the photo collection. Use any of those systems, and augment it by making use of OS X's extremely useful tagging feature.
Furthermore, there are many applications, such as the ones made by Ironic Software, that allow you to search, organize, and work with your files in very powerful ways using those tags. Since the tagging system is common to all of them you are not tied to any particular application.
The only downside of this is that you do become dependent on OS X at least until other systems implement tagging.