Any unitary $U$ acting on $N$ qubits can be decomposed in a finite product $U=U_1U_2...U_n$ where every $U_i$ acts on only 2 qubits, for example through decomposition in CNOT, phase shifts and 1 qubit rotations.
Is there a theorem that gives $n_{min}$ the minimum number of 2 qubit gates to build any fixed size unitary? For a lower bound, $n_{min}\geq N$ given that every qubit need to be used at least once.
In contrast to the answer by Bertrand, I will assume that along with a $CNOT$ gate we have arbitrary single-qubit unitaries on our disposal. In this case, one can derive the theoretical lower bound on the number of $CNOTs$ neseccary to decompose an arbitrary $n$-qubit unitary $$ L:=\#\text{CNOTs} \geq \frac14\left(4^n-3n-1\right) \label{TLB} $$ In fact, the derivation of this bound is quite intuitive and I will sketch the proof. A general $d\times d$ unitary has $d^2$ real parameters. For $n$ qubits $d=2^n$. Single one-qubit gate has 3 real parameters. However, we can not just keep stacking 1-qubits gates like here
$\approx$ 
because any sequence of one-qubit gates applied to the same qubit can be reduced to a single one-qubit gate and hence can have no more than 3 parameters. That means, that without CNOTs we can only have 3n parameters in our circuit, 3 for each one-qubit gate. This is definitely not enough to describe an arbitrary unitary on $n$ qubits which has $d^2=4^n$ parameters.
Now, adding a single CNOT allows to insert two more 1-qubit unitaries after it, like that
At the first glance this allows to add 6 more parameters. However, each single-qubit unitary can be represented via the Euler angles as a product of only $R_z$ and $R_x$ rotations either as $U=R_z R_x R_z$ or $U=R_x R_y R_z$ (I do not specify angles). Now, $CNOT$ can be represented as $CNOT=|0\rangle\langle 0|\otimes I+|1\rangle\langle 1|\otimes X$. It follows that $R_z$ commutes with the control of $CNOT$ and $R_x$ commutes with the target of $CNOT$, hence they can be dragged to the left and joined with preceding one-qubit gates. So in fact each new $CNOT$ gate allows to add only 4 real parameters:
That's it, there are no more caveats. Thus, the total number of parameters we can get with $L$ CNOTs is $3n+4L$ and we need to describe a $d\times d$ unitary which has $4^n$ parameters. In fact, the global phase of the unitary is irrelevant so we only need $3n+4L \geq 4^n-1$. Solving for $L$ gives the theoretical lower bound. Pretty cool!
There is an algorithm, called quantum Shannon decomposition (see paper), which gives an exact compilation of any unitary with the number of $CNOTs$ roughly twice as much as required by the theoretical lower bound.
In a couple of recent papers (ref 1, ref 2) a numerical optimization approach was explored. It was found that (at least for small qubit numbers) the theoretical lower bound can always be achieved with an exceptional fidelity (hinting that the exact compilation can also be possible). What I find especially interesting about these results is that they also generalize to limited connectivity, apparently without any overhead. For example, the number of $CNOTs$ needed to decompose a random 5-qubit unitary on a line topology (where only neighboring qubits can interact) is the same as on the fully connected topology.
A very important disclaimer is in order here. Formally, the set of unitaries which does not have to obey the theoretical lower bound has measure zero in the space of all unitaries of a given size. However, in actual quantum algorithms most of the time only very specific gates are used (say multi-controlled gates) and those do fall in this special set where the theoretical lower bound does not apply. This means that for most multi-qubit gates of practical interest much more efficient decompositions exist.
Let me try to reformulate your question: Given a Universal Set of Quantum Gates $\mathcal{G}$; and some $n$-bit Unitary $U$. Can we find some $q$ such that $q$ is the minimum number of gates selected from $\mathcal{G}$ to have the effect of $U$ on $n$ qubits? (Note: I changed some variables since typically $n$ is the number of bits and $N=2^n$ is the dimensions of our Hilbert Space).
Finding a direct and general expression for such an $q$ would be extremely difficult and it's namely because of all possible gatesets that we may be provided with. Think in the classical case how a universal set of gates can be $\{AND, OR, NOT\}$ or $\{NAND\}$ or $\{MUX\}$ or... For some boolean expression; if you are given a certain universal gateset it completely changes your optimization strategy and correspondingly your minimum number of gates used. The same is true for the quantum case; there really isn't some magical and general formula (although there are definitely specific examples for which $q$ can be found)...but there is something close!
The Solovay-Kitaev Theorem is incredibly important to quantum computing and it is related to the question you ask. It states the following: There exists some constant $c$ such that for any unitary $U\in SU(2)$ there is a set of $S$ gates from any Universal Set of Gates $\mathcal{G}$ such that $|S|=O(\log^c(\frac{1}{\epsilon}))$ for some $\epsilon>0$.
