You certainly won't have to "invent" it from scratch - GPS/INS fusion is a topic well covered in literatur. Just two well known books:
- Farrel: http://books.google.de/books/about/The_Global_Positioning_System_Inertial_N.html?id=fW4foWASY6wC&redir_esc=y
- Groves: http://www.amazon.com/Principles-Multi-Sensor-Integrated-Navigation-Applications/dp/1580532551).
As others have pointed out (e.g. Kalman Filter for Android), there are also implementations of Kalman filters in Java / for Android.
The problem with Kalman filtering in your specific case is that need to fulfill several requirements for implementing a Kalman filter*. Theoretically, you need to make sure that the noise (unmodelled measurement errors) are white and uncorrelated over all times. The problem is that you don't get the raw GPS measurements from the internal receiver (which could approximately be considered white) but rather an already filtered solution (which definitely exhibits time-correlations).
Another problem is, that in a Kalman filter you need to do some tuning, i.e. you need to set parameters like measurement noise. Such parameters depend on the quality of the sensors used - so they differ between different devices. This might degrade your estimation quality on some devices.
That being said, there might be several solutions:
Use the velocity to extrapolate the position in between position updates. (I haven't done this on Android, but this question might help to get the velocity.) If the user's velocity doesn't change too frequently (compared to the position update frequency), this should work quite well in most cases.
Implement a full Kalman filter: Combining absolute position measurements with Accelerometers is pretty common as noted by the books cited above, even with cheap MEMS grade inertial sensors. In order to reduce the errors induced by the Acc sensors, estimate these in the Kalman filter state vector. Usually, a Kalman filter estimates position, velocity, attitude and Acc/Gyro biases in one filter. You can drop attitude and gyros if you want to assume that these are known well enough. Even though your sensors might exhibit many more errors, estimating biases is often good enough for estimating in between position updates.
Implementing a full Kalman Filter could also mean you account for time correlations of your measurements, e.g. with techniques called Schmidt-Kalman-Filter (see books cited above). This might also mean you use Adaptive Kalman Filtering to estimate some parameters of your filter to account for different sensors in different devices. Note, however, that such things require a little experience in the field of navigation: The implementation is usually easy - just a few lines of matrix operations, but the tuning can be time-consuming. But that doesn't mean you shouldn't try it!
- Only use the bias estimation of the above filter: With the Acc bias estimated, you can improve the first method (extrapolating the position with the velocity) by also extrapolating the velocity with the Accelerometer measurements.
*from a theoretical standpoint - you can always ignore theory and just try. Sometimes it will still work :-)