http://drupal.org/node/87195 – Thanks!

In drupal 6, You might not get the tabs if your menu tree does not have any parent.
ie, if here is our requirement.

We need two tabs
1) search/all (default and /search should also point to this)
2) search/artist

Here is what you do

In main view
PATH: search/all
MENU: Default menu tab
Menu Settings
Parent menu item: Normal menu item -> anything

In alternate view
Path: search/artist
MENU: Menu Tab