Bid units can only be placed in territories you control at the start of the game, or in sea zone immediately adjacent to territories you control at the start of the game.
And that is per NATION, not per SIDE. So Germany can only place their bid units in or adjacent to GERMANY controlled territories, and Japan can place their bid units only in or adjacent to THEIR territories. Germany cannot place in Japan controlled territory and vice versa.
Also, I think that in Classic you cannot place bid units in an enemy occupied sea zone (so Germany cannot place units in the sea zone around UK even though it borders both Western and Norway that are Germany controlled.