Given two functions $f(n)$ and $g(n)$, is it possible that $f(n) = O(g)$ and that $g(n) = O(f)$?
If the answer is yes, I have a follow-up: if $f(n)$ and $g(n)$ are Big-O of each other, does that also mean that they are Big-Omega of each other? Because if that is the case, that would mean that they are also Big-Theta of each other.
On
Is it possible? Yes. A simple example: $f=g$.
What does it imply? This is equivalent to saying that $f=\Theta(g)$. To see why:
If $f=O(g)$, there exists $c>0$ and $N \geq 0$ such that $$ \forall n \geq N, \qquad f(n) \leq c\cdot g(n) \tag{1} $$
If $g=O(f)$, there exists $c'>0$ and $N' \geq 0$ such that $$ \forall n \geq N', \qquad g(n) \leq c'\cdot f(n) \tag{2} $$
Combining (1) and (2), and choosing $M\stackrel{\rm def}{=}\max(N,N')$, $\alpha\stackrel{\rm def}{=}\frac{1}{c} > 0$, $\beta \stackrel{\rm def}{=} c'$, we get that there exist $M\geq 0$, constants $\alpha,\beta>0$ such that $$ \forall n \geq M, \qquad \alpha f(n) \leq g(n) \leq \beta f(n) \tag{3} $$ which by definition means $f=\Theta(g)$. This should answer both your questions.
The answer is yes.
One may take $f(n)=n$ and $g(n)=2n+1$, as $ n \to \infty$, one has $$ \left|\frac{f(n)}{g(n)}\right|=\frac{n}{2n+1}\le \frac12 \implies f=O(g) $$ and $$ \left|\frac{g(n)}{f(n)}\right|=\frac{2n+1}{n}\le 3 \implies g=O(f). $$