What exactly is meant by a “niced” and an “un-niced” user process

The proportion of the processor time a particular process receives is determined by the relative difference in niceness between it and other runnable processes.

The Linux Completely Fair Scheduler (CFS) calculates a weight based on the niceness. The weight is roughly equivalent to 1024 / (1.25 ^ nice_value). As the nice value decreases the weight increases exponentially. The timeslice allocated for the process is proportional to the weight of the process divided by the total weight of all runnable processes. The implementation of the CFS is in kernel/sched/fair.c.

The CFS has a target latency for the scheduling duration. Smaller target latencies yield better interactivity, but as the target latency decreases, the switching overhead increases, thus decreasing the overall throughput.

Given for instance a target latency of 20 milliseconds and two runnable processes of equal niceness, then both processes will run for 10 milliseconds each before being pre-empted in favour of the the other process. If there are 10 processes of equal niceness, each runs for 2 milliseconds each.

Now consider two processes, one with a niceness of 0 (the default), the other with a niceness of 5. The proportional difference between the corresponding weights is roughly 1/3, meaning that the higher priority process receives a timeslice of approximately 15 milliseconds while the lower priority process receives a timeslice of 5 milliseconds.

Lastly consider two processes with the niceness values of 5 and 10 respectively. While the absolute niceness is larger in this case, the relative differences between the niceness values is the same as in the previous example, yielding an identical timeslice division.

Since linux 2.6.12, that depends on the value of the RLIMIT_NICE limit (ulimit -e). Which can take values from 0 to 40. That limit is more the limit on the priority of the process (the greater that number, the higher the priority a user can set for a process).

You'll notice the default value is 20 on ubuntu 10.04 and 0 in Debian jessie for instance.

A value of n for that limit means that a process without the CAP_NICE capability can only increase a process priority to up to n, which means decrease niceness down to a niceness of 20 - n. So for a value of 0, that means no non-privileged user can lower the niceness below 20, so no non-privileged user can lower the niceness.

With a value of 20, non-privileged users can decrease the niceness back to 0.

It's up to the administrator to choose whether they allow users to lower their process priority, and to what level by setting the hard limit for that.

As to why an administrator may not want users to lower their process priority, see Flup's answer.