Besides the usual deterministic DFS/BFS approaches, one could also consider a randomized algorithm. I will shortly describe a randomized algorithm for deciding if two vertices $s$ and $t$ are connected. It can also be used to decide if the whole graph is connected. The main benefit is that this method requires $O(\log |V|)$ bits of space, whereas a BFS/DFS requires $\Omega(|V|)$ space.
The cover time of an undirected graph $G=(V,E)$ is the maximum over all vertices $v \in V(G)$ of the expected time to visit all of the nodes in the graph by a random walk starting from $v$. Using some theory of Markov chains, it is not too hard to prove the cover time of $G$ if bounded from above by $4|V|\cdot|E|$.
The algorithm for deciding if $s$ and $t$ are connected is simple:
Input: two vertices s,t
1. Start a random walk from s.
2. If t is reached within 4|V|^3 steps, return true. Otherwise, return false.
Clearly, if there is no path between $s$ and $t$ the algorithm returns the correct answer. If there is a path, the algorithm errs if it is not found within $4|V|^3$ steps. The cover time of $G$ is bounded from above by $4|V||E| < 2|V|^3$. Using Markov's inequality, the probability that a random walk takes more than $4|V|^3$ steps to reach $t$ from $s$ is at most $1/2$. In other words, the algorithm returns the correct answer with probability $1/2$, and only errs by saying $s$ and $t$ are not connected when they in fact are.