As others have mentioned, it is usually not easy to find the geodesics of a given surface, so let me address some of your other questions.
Let's start with a simple case. If a surface $S$ in $\mathbb{R}^3$ is the graph of a function $z = f(x,y)$, then the metric $g$ can be represented in coordinates by the matrix $g = \begin{pmatrix} 1 + (f_x)^2 & f_xf_y \\ f_xf_y & 1 + (f_y)^2 \end{pmatrix},$ where subscripts denote partial derivatives.
In the case of $z = x^2 + y^2$, for example, we have $g = \begin{pmatrix} 1 + 4x^2 & 4xy \\ 4xy & 1 + 4y^2 \end{pmatrix}.$
More generally, if a surface $S$ in $\mathbb{R}^3$ is given by a local parametrization $\phi(x,y) = (\phi^1(x,y), \phi^2(x,y), \phi^3(x,y))$, then the metric $g$ can be represented by the matrix $g = \begin{pmatrix} \langle \phi_x, \phi_x\rangle & \langle\phi_x, \phi_y\rangle \\ \langle\phi_y, \phi_x\rangle & \langle\phi_y, \phi_y\rangle \end{pmatrix},$ where I am using the notation $\langle v, w\rangle = v \cdot w$ to denote the inner product (or "dot product") in $\mathbb{R}^3$. For example, $\langle \phi_x, \phi_y\rangle = \langle (\phi^1_x, \phi^2_x, \phi^3_x), (\phi^1_y, \phi^2_y, \phi^3_y)\rangle = \frac{\partial\phi^1}{\partial x}\frac{\partial\phi^1}{\partial y} + \frac{\partial\phi^2}{\partial x}\frac{\partial\phi^2}{\partial y} + \frac{\partial\phi^3}{\partial x}\frac{\partial\phi^3}{\partial y}.$ The case above where the surface is given as the graph of the function $z = f(x,y)$ is the special case where $\phi(x,y) = (x,y, f(x,y)).$
Note that the metric (tensor) was classically called the first fundamental form.
Now, I personally like to think of geodesics as unit speed curves that have zero geodesic curvature (rather than as curves which satisfy the geodesic equation).
To say that a curve $\alpha(t) = (x(t), y(t), z(t))$ is unit speed means that $|\alpha'(t)| \equiv 1$. (It is a fact that all geodesics have constant speed.) To say that a curve $\alpha$ has zero geodesic curvature means, well, that the geodesic curvature $\kappa_g \equiv 0$, where $\kappa_g = \langle N \times \alpha', \alpha'' \rangle,$ where $N$ is the unit normal vector to the surface. A nice apparatus for thinking about this definition is the Darboux frame.
Anyway, here are three more geometric facts that might help you in your search for geodesics, or at least your intuition for them:
Fact 1 (Corollary to Meusnier's Theorem): Let $\Pi$ be a plane that intersects a surface $S$. If at each point of intersection the plane $\Pi$ is perpendicular to the tangent plane to $S$, then the curve of intersection is a geodesic. (Such a curve is called a normal section.)
Fact 2: On a surface of revolution, every meridian is a geodesic.
Fact 3 (Clairaut's Theorem): Let $S$ be a surface of revolution, let $\alpha$ be a curve on $S$ with unit speed, let $\rho\colon S \to \mathbb{R}$ be the distance of a point of $S$ to the axis of rotation, and let $\psi$ be the angle between $\alpha'$ and the meridians of $S$.
Conclusion: If $\alpha$ is a geodesic, then $\rho \sin \psi$ is constant along $\alpha$. Conversely, if $\rho \sin\psi$ is constant along $\alpha$, and if no part of $\alpha$ is part of some parallel of $S$, then $\alpha$ is a geodesic. (cf. Clairaut's Relation.)
Remarks: I usually visualize Fact 1 by considering a right circular cylinder (try this!). Fact 2 should give you some of the geodesics on the elliptic paraboloid $z = x^2 + y^2$. Fact 3 can be used to determine the geodesics on the pseudosphere.