First off, I wanted to let you know that this is not necessarily intuitive, and there's very hacked methods of doing this. Another thing that I want to mention is that I did this in Drupal 7 with Views 3. However, one of the things that I think is most different is the UI. So text descriptions should be able to guide you. :)
The way that I went about doing this is as follows:
In Views, I created a block which is to display the content type of the related items (mine was recipes). I added the fields which I wanted to appear, which were just pictures and titles. Then in Contextual Filters (I think D6/Views2 calls this arguments), I added two.
The first is "Content: Nid" and I configured it as follows:
When filter value is not available => Provide default value => Type: Content ID from URL. Under "more" (not sure what V2 calls it), there's an option called "exclude", which if selected, the numbers entered for the filter will be excluded rather than limiting the view. This is great because it essentially says, "Return me the list of everything of this content type EXCEPT this one that I'm on."
The second filter is "Content: Has taxonomy term ID". This one was a bit trivial because I want to provide relationships on multiple vocabularies of taxonomy terms. So it's configured as follows: When the filter value is NOT available => Provide Default Value => Taxonomy term ID from URL => Load default filter from node page => Limit terms by vocabulary => Selected my vocabularies => Multiple-value handling -> filter to items that share any term.
When the filter value IS available or a default is provided => Specify validation criteria => Validator = Taxonomy term, with my previous chosen vocabularies selected again => Filter value type => Term IDs separated by , o + . Under "more", I checked "allow multiple filter values to work together."
This was the way that I was able to get the related content. I specified the amount of results that I wanted in the pager.
Hope that this helps!