The answer is completely described by the Frobenius–Schur indicator, $$v_2(\chi) = \frac{1}{|G|}\sum_{g\in G} \chi(g^2)$$
which is covered in chapter 4 of Isaacs's Character Theory of Finite Groups. In particular, we have the Frobenius–Schur theorem, as given on page 58 of Isaacs's CToFG:
Theorem: If $\chi$ is an irreducible (ordinary, complex) character of the finite group $G$, then $$v_2(\chi) = \begin{cases}
1 & \chi \text{ is the character of an irreducible real representation} \\
0 & \chi \text{ takes complex values } \\
-1 & \text{otherwise}
\end{cases}$$
If $v_2(\chi)=1$, $\chi$ is the character of a real representation. If $v_2(\chi)=0$, then $\chi + \bar \chi$ is the character of a real representation. If $v_2(\chi)=-1$, then $2\chi = \chi + \bar \chi$ is the character of a real representation.
The following is Lemma 9.18 (more or less) in Isaacs's CToFG:
Proposition: If $\chi$ is a (ordinary, complex) character of the finite group $G$, then $\chi + \overline{\chi}$ is the character of a real representation of $G$. More generally, if $K \leq F$ are fields of characteristic 0 and $\chi$ is the character of a (ordinary) $F$-representation of $G$, then for every $\sigma \in \operatorname{Gal}(F/K)$, $\chi^\sigma = g \mapsto \sigma(\chi(g))$ is the character of a (ordinary) $F$-representation of $G$, and $$\sum_{\sigma \in \operatorname{Gal}(F/K)} \chi^\sigma$$ is the character of a $K$-representation.
Proof: If $\chi$ is the character of the representation $X$, then consider the representation $X \otimes_{\mathbb{C}} \mathbb{C}_\mathbb{R} \cong X \oplus \bar X$ obtained by replacing the complex entries $a+bi$ of $X$ with the block matrices $\begin{bmatrix} a & b \\ -b & a \end{bmatrix}$. The resulting matrix has trace $\chi(g) + \bar\chi(g)$, since we replace each diagonal entry $a+bi$ with a matrix of trace $2a$. The general case is similar: just choose a $K$-basis of $F$, and write out the associated matrix representation of $f \in F$ in its action on the $K$-vector space $F$. $\square$
Since you mention GAP, I'll mention the indicators of a character table are computed using Indicator( chartable, 2) and that since every complex, ordinary representation of $G$ is a representation over the field CF(Exponent(G)), the $\sigma$ appearing in the Galois group are given by chi -> GaloisCyc(chi,k) for $k$ relatively prime to $G$. In particular, $k=-1$ is complex conjugation. To compute the matrices of the $K$-representation from the $F$-representation as described in the proof, you can use BlownUpMat(Basis(AsVectorSpace(K,F)),mat).
The function RationalizedMat can be applied to a character table to compute some smaller sums where one needs to multiple by the so called Schur index as in Geoff Robinson's answer: for example, it would take a real character and leave it real, even if its indicator were $-1$. However, for Brauer characters (where the Schur indices are always 1), it can be very handy.
At any rate, chapters 4, 9, and 10 of Isaacs's textbook are great for understanding how characters work over different fields of characteristic 0 and how that relates to the power maps of the character table.
To clarify what I am specifically interested in knowing, if I have found some irreducible representations of a group $G$. Say I have $\chi_1, \dots, \chi_m$. I know I haven't found all of them because I know the number of conjugacy classes. Then, say, I some other non-irreducible character $\chi$ and I know, say, that this is the character of some representation. Then I subtract a linear combination of $\chi_1, \dots, \chi_m$, and define the class function $\psi = \chi - (a_1\chi_1 + \dots + a_m\chi_m)$. How do I know whether this $\psi$ is the character of some representation?
This question is much easier than your general question; assuming the $a_i$ are nonnegative integers, the answer is if and only if $\langle \chi, \chi_i \rangle \ge a_i$ for all $i$. This follows from:
Lemma: A class function $\chi$ is the character of a representation iff for every irreducible character $\chi_i$, $\langle \chi, \chi_i \rangle$ is a nonnegative integer.
Proof. If $\chi$ is the character of a representation $V$ then $\langle \chi, \chi_i \rangle$ is the multiplicity of the irreducible representation $V_i$ corresponding to $\chi_i$ in $V$, so this condition is clearly necessary. On the other hand, if this condition holds, then $\chi = \sum \langle \chi, \chi_i \rangle \chi_i$, and hence the direct sum of $\langle \chi, \chi_i \rangle$ copies of $V_i$ is a representation with character $\chi$. $\Box$
If you set $a_i = \langle \chi, \chi_i \rangle$ then you've removed the components of the representation corresponding to $\chi$ which correspond to the irreducibles with character $\chi_i$. So all you're left with is the components corresponding to the irreducibles you haven't found yet.
Best Answer
This is a well-established theory, which is very nicely presented in the second volume of the two-volume work of Curtis and Reiner. Here is the gist of it:
Since a rational representation is also a complex representation, you still have character theory to help you. In particular, a rational representation is still uniquely determined by its character, which, of course, only take values in $\mathbb{Q}$.
So suppose that you wanted to do the converse: start with the knowledge of all the complex representations (including the full character table), and construct all the irreducible rational ones. The absolute Galois group of $\mathbb{Q}$ acts on the set of complex representations by acting on each entry in each matrix, and so also acts on the set of characters. If $\chi$ is the character of an irreducible rational representation, then it must be invariant under the Galois action. In particular, if $\phi$ is an irreducible complex character sitting inside $\chi$, then every Galois conjugate $\phi^\sigma$ also has to sit in $\chi$ with the same multiplicity. So the first step is to take an irreducible complex character $\phi$ and to "rationalise" it by $\chi = \sum_{\sigma\in \text{Gal}}\phi^\sigma$, with the sum running over the distinct Galois conjugates of $\phi$.
So now you have a $\mathbb{Q}$-valued character, but it does not mean that the corresponding representation can be realised over $\mathbb{Q}$ (as an example, think of the standard representation of the quaternion group $Q_8$). However, there is a unique minimal integer $m(\chi)$ such that $m(\chi)\chi$ can be realised over $\mathbb{Q}$, and this representation is in fact irreducible over $\mathbb{Q}$. This $m(\chi)$ is called the Schur index of $\chi$, and is also nicely treated in Curtis and Reiner, but also in Isaacs for example. It is now easy to see that all irreducible rational representations arise in this way. If you are interested in general number fields, then you only have to average over the Galois conjugates over that field, but you may still have a Schur index flying around.
The answer to your question about the number of irreducible rational representations is really neat: it is equal to the number of conjugacy classes of cyclic subgroups of $G$ (as opposed to conj classes of elements, like in the complex case). I seem to remember that this is proven, among other places, in Serre's book on representation theory. This is one of the ways of stating Artin's induction theorem.