I know they're male and female, and different colors, but other than that...
There is not much difference between them. One is male, one is female. Nidoking has slightly better attack and speed, while Nidoqueen has slightly better defense. And they look a bit different.
The reason they are separate species in the pokedex is because the original Red/Blue/Yellow games did not have genders so they had separate evolutionary lines for the males and females.