How can I show that $\mathbb F_{11}[x]/(x^2+1)$ has 121 elements?
Though, it is intuitively clear because there are 121 one degree polynomials, but how do I prove it rigorously?
Your intuition is very good. We can prove this rigorously by appealing to the division algorithm: for all $f\in F[x]$, there are unique $q,r\in F[x]$ such that $\deg(r)<\deg(x^2+1)=2$ and $$f=(x^2+1)q+r.$$ Thus, any $f\in F[x]$ has a unique $r=a_0+a_1x\in F[x]$ such that $f\equiv r\pmod{ x^2+1}$. Thus, there are at most 121 equivalence classes modulo $x^2+1$, i.e. there are at most 121 elements of $F[x]/(x^2+1)$. But uniqueness also tells you that $$a_0+a_1x\equiv b_0+b_1x\pmod{x^2+1}\iff a_0=b_0\text{ and }a_1=b_1$$ so all 121 equivalence classes of degree < 2 polynomials are distinct. Thus, there are exactly 121 equivalence classes, i.e. there are 121 elements of $F[x]/(x^2+1)$.
This generalizes to any degree $n$ polynomial, regardless of whether it is irreducible; however, if $g\in F[x]$ is not irreducible; the ring $F[x]/(g)$ will not be a field.
Prove that in general given a field $k$ and a polynomial $p$ of degree $n$ then $k[x]/(p)$ is an $n$-dimensional $k$-space, and so, in fact isomorphic to $k^n$ as vector spaces. So, for your example $F[x]/(x^2+1)\cong F^2$ and since $F$ has eleven elements $F^2$ has $121$.
Perhaps, I should give a hint on how to do this. You know that $\{1,x,x^2,\cdots\}$ generates $F[x]$ and so $\{1+(x^2+1),x+(x^2+1),x^2+(x^2+1),\cdots\}$ generates $F[x]/(x^2+1)$. Show that, in fact, each $x^n+(x^2+1)$ for $n\geqslant 2$ can be obtained from $1+(x^2+1)$ or $x+(x^2+1)$ and conclude that the set $\{1+(x^2+1),x+(x^2+1)\}$ is a generating set for $F[x]/(x^2+1)$. Note then that this set is trivially linearly independent (perhaps a degree argument noting what it would mean if they were equal in terms of $x^2+1$) and then conclude.