Complete story mode with all characters, then get a high score as Hayate in Survival or Time Attack and enter your name as EIN to unlock both Ein and Random Select.
For all characters, picking up a Prototype Xbox item in survival mode will automatically unlock a new costume for them.
Some costumes have multiple ways to be unlocked. If you see a costume with multiple clear conditions, it does not mean you have to clear all of them, but rather that you have more than one way to unlock it.
Note that all costumes except Kasumi's C3 and Ein's C3 cannot be unlocked in the US version of DOA3. You will instead need the Booster Disc or a copy of DOA2 Ultimate to add costumes to your game.