Question: I want to know whether Perl is installed by default on all Unix-based operating systems. Since I want to write server-side programs, I need to choose between Perl and C.

Answer: 
I'm not sure whether Perl is standard on all Unix server installs. I'm not even sure what that means - a server is a piece of hardware, it doesn't have to come with *any* specific software (not even an OS).

I don't think this should be the deciding factor anyway. You can always compile Perl, or distribute Perl with your program. The factors in choosing a language for your project are:

1) Which languages map well to the domain? Using C for a text processing program would be a mistake, this is where Perl and Python shine (perhaps Ruby also?). Using Perl for your hard real time embedded application would probably be a mistake.

2) What experience do the people on the team have?

3) What skills would you (or your company) like to develop? It might be okay to use a new language if this is something that will give you or your company an edge in the long run. The best example of this would be Ericsson switching to Erlang.
Most linux distros DO include it by default. However, we got a stack of AIX machines a few months back running AIX 7.1 and none of them have perl installed.

The very, very broad answer is no, you cannot assume that every Linux or Unix system you buy will have Perl installed on it.