The book The Power of Habit brought up a tale in the first chapter about a man who lost the capability of storing long term memory because of brain damage. He could not remember conversations or TV shows he watched just 10 minutes ago. He could still walk and have normal conversations, just that he would repeat the same questions.
However, his man was able to learn new things because a part of his brain (the basal ganglia) stored habits. He kept his old habits, like cooking bacon for himself every morning. He developed new habits like walking outside and coming back, even though he could not remember the road back to his house.
They did a basic memory test by joining objects to different colored cardboard rectangles. Under some of the rectangles the word "correct" was written. Most people can easily memorize which objects are "correct" within a few minutes. As this man had brain damage, he could not remember it no matter how hard he tried.
After a few days of repeating the same tests, he got up to 85% success, then 95% success. He did not remember any of this. To him, he had never seen the objects before and had a gut feeling of which objects were "correct". The inference here is that they were stored in the part of the mind that stores routines/habits. (Duhigg, 2012)
I would assume that a "gut feeling" works in a similar manner. You see have seen certain patterns repeated several times, and it develops into a routine in your brain. Long after these patterns have been removed from your conscious memory, you still have them stored somewhere in the form of a routine. They're especially noticeable with trivia knowledge. People who work in the fire department develop a 'sixth sense' for dangerous situations because they've observed the same cues that occur before a dangerous situation multiple times.
To summarize, a gut feeling is likely a recollection of certain micropatterns that you've seen several times before.
Source: Duhigg, C. (2012). The Habit Loop: How Habits Work, The Power of Habit: Why We Do What We Do in Life and Business.