Relation between VCO's (Voltage Controled Oscillator's) Frequency and Voltage
VCOs are made with various technologies for various purposes, so the answer is 'it depends'.

Some low frequency VCOs are intended to have very linear relationship, perhaps to be used as a voltage to frequency converter. They often turn the input voltage into a current, to swing the voltage on a capacitor over a fixed range. This sort of architecture departs from linearity at low frequency, when fixed leakage currents become a significant part of the controlled current, and at high frequency, when switching propagation times become a significant part of the output period. Without the intention to have a linear relationship, VCOs may well depart significantly from nominal linearity. 

There is a class of VCO that sacrifices frequency linearity for period linearity, using a constant current to swing a capacitor between voltages dependent on the input. Here the propagation delay time is an additive constant onto the period, leakage currents are with respect to a fixed current, and a t=mV+c straight line can be accurately defined between input voltage and output period.

High frequency VCOs for RF work usually use varactors in LC oscillators. These designs are not usually driven by thoughts of linearity, but noise, spectral purity, and 'oh, if it's not too nonlinear, that would be handy!' Although the capacitance is a very nonlinear function of the applied voltage, the fact that frequency varies as the square root of capacitance means that even in wide range VCOs, the change in FM sensitivity across the range can end up being quite small, often less than a factor of 2.

The best measurement-grade voltage to frequency converter I have come across used a 4046 PLL fed back with a frequency discriminator based on a HC123 monostable.