Reading in the Allergies forum will be really helpful in getting started. Tons and tons of old threads. List several breakfasts, lunches, and dinners that will work for your situation. Dinner is pretty easy, other starches like rice, potatoes, quinoa, corn (tortillas?), lentils, those are easy ones to just sub in for wheat pasta or bread/rolls. There are other GF grains, they're just less familiar.
Gluten: wheat, spelt, barley, rye, kamut, triticale, maybe a couple more less common wheat-related grains
Oats are usually x-contaminated with wheat unless they say gluten free and have a protein that is similar--some people react to it as well even though it's not quite the same
Read more in the Allergies forum, some people are very sensitive to cross-contamination and some are not (DD is not, I don't think, whereas DS and I were quite sensitive early on, now 3 years later we are not so much), for discussion on things like toasters and non-stick cookware and plastic food storage containers. May not be an issue, but knowing it's a possibility keeps it at the back of your mind to consider.
Breakfast: eggs and fruit; bacon or breakfast sausage and fruit; cooked grains like buckwheat, amaranth, millet (they can cook up similar to oatmeal); GF bread (read a lot for good brands or try a mix like Bob's Red Mill mix); some breakfast cereals are GF and you can choose a non-dairy milk (personally I wouldn't add in a lot of new soy when you cut out dairy given how cross-reactive milk and soy are); breakfast tacos with corn tortillas. More ideas in Allergies, I am not very creative with breakfast.
I didn't do a food diary at the beginning, I did one later to try to figure out my son's face rashes, but at first, you could just wait and see what changes and what doesn't and then start journalling if there are symptoms that are coming/going.
I don't think *I* would've felt better without taking out both gluten and dairy. Some folks have different symptoms for each--but I wouldn't take out dairy, for example, see no difference, then add it back and THEN take out gluten. At some point, you want to have all the suspected foods removed at the same time.
Do you suspect celiac? I don't for us, we're gluten intolerant but I'm almost certain none of us has celiac. Depending on how you test, you may need to continue eating gluten (the official test requires that, there are alternative tests that don't), and then you'd need to decide if a celiac diagnosis is helpful for you. Lots of threads in Allergies about that, people decide both ways on whether the diagnosis is helpful for them in their situations.