When you defeat the following characters at the indicated area they will become unlocked for VS mode.

Unlock Smoker:
Defeat him just before you enter Fossil Beach.

Unlock Eneru:
Defeat him at the Ruins Zone area in Story mode.

Unlock Mihawk:
Beat him at the Fossil Beach area in Story mode.

Unlock Arlong:
Beat him at the Cave area in Story mode.

Unlock Survival Mode
The following characters must ALL be defeated in vs. Mode to be able to unlock Survival Mode. The locations given are the first location that you will first encounter each enemy.

Unlock World Government Agent:
Defeat one in the Ruins Zone.

Unlock Sword Demon Soldier:
Defeat one in the Cave Zone.

Unlock Cluster Demon Soldier:
Defeat one in the Cave Zone.

Unlock Crimson Demon General:
Defeat one in the Cave Zone.

Unlock Bazooka Marine:
Defeat one in the Seaside Zone.

Unlock Blue Demon General:
Defeat one in the Cave Zone.

Unlock Marine Corps Chief:
Defeat one in the Jungle Zone.

Unlock Normal Marine:
Defeat one in the Seaside Zone.

Unlock Pistol Pirate:
Defeat one in the Jungle Zone.

Unlock Sabre Pirate:
Defeat one in the Jungle Zone.

Unlock Knuckle Pirate:
Defeat one in the Ruins Zone.