Remember that work is a transition function - not a state function. You only do work over a distance, not at a point. So when using $W=F\Delta x$ in integral-form we must remember the edges of the integral:
$$W=\int_{r_i}^{r_f} F\;dx$$
Let's choose the positive axis outwards from Earth (force is negative $-F_g$ and displacement is $r_f<r_i$) and calculate work done on a falling object:
$$\begin{align}
W&=\int_{r_i}^{r_f} (-F_g)\; dx\\
&=\left[-\left(-\frac{GM}x\right)\right]_{r_i}^{r_f}=\left[\frac{GM}x\right]_{r_i}^{r_f}\\
&=\frac{GM}{r_f}-\frac{GM}{r_i}
\end{align}$$
$r_f<r_i$, and because they are in the denominators, $\frac{GM}{r_f}>\frac{GM}{r_i}$ and thus work $W$ is positive.
Or we can try with another choice of axis, e.g. from the starting point of the falling object and inwards towards Earth (force is positive $+F_g$ and displacement is $r_f>r_i$):
$$\begin{align}
W&=\int_{r_i}^{r_f} F_g\; dx\\
&\left[-\frac{GM}x\right]_{r_i}^{r_f}\\
&=\left(-\frac{GM}{r_f}\right)-\left(-\frac{GM}{r_i}\right)\\
&=\frac{GM}{r_i}-\frac{GM}{r_f}
\end{align}$$
In this case $r_i<r_f$, so $\frac{GM}{r_i}>\frac{GM}{r_f}$ and work is still positive. Choice of axis doesn't matter - a choice just has to be made to get the signs clear.
This can also be looked at from pure energy.
Gravitational potential energy is:
$$U=\int F \;dr=-\frac{GM}r$$
Work done by Earth on something falling is:
$$\begin{align}
W&=\Delta K=U_i-U_f\\
&=-\frac{GM}{r_i}-\left(-\frac{GM}{r_f}\right)\\
&=\frac{GM}{r_f}-\frac{GM}{r_i}
\end{align}$$
Again work $W$ will be positive.
A sign rule-of-thumb is always the formula: $W=Fr$: Work is positive if force and displacement are in the same direction, and negative if opposite.
Gravity therefor always does positive work on a falling object. But was rising like a weatherballoon, the work done by gravity would be negative. Negative work just means that your efforts don't really work; the object still moves in another direction than in which you are pushing/pulling.
