"I like using Search Folders in Outlook 2003, but one thing that I'm stuck on is how can I create "or" conditions, such as:

"I want to see all messages that have this flag or that flag". It appears to me that everything is always an "and" condition..."

Search Folders (as well as Advanced find, Automatic formatting, and View's Filter) uses AND to tie different criteria together.

You can only OR conditions within one criteria - From Mary OR Bob - and can either enter it on one line, typing OR between the criteria as above or enter it on two rows:
From Mary
From Bob

In most cases, you'll need to create the filter using the Advanced tab, not the fields on the General or More choices tabs. Flags fall into "most cases" - and creating the filter on Advanced tab will allow you to create a Search Folder for two or more specific flag colors.