Although I started in OOP, I often find that my thoughts on a new problem drift closer to one of two much more basic methodologies.
1) What are the data and structures that I'd need?
This is identical to the OOP "what objects do I need" but more basic, easier to understand. Say I have the requirement "Read an address book file, send an email to all the email addresses in it." I know I'll need to keep a collection of address records as I read them from the file, so I know I'll need a collection. Usually a List or Array is a good start. If I need "named access" I'll use a dictionary/map. More specific data structures fill particular roles that you'll learn as you go (queues, dequeues, stacks, sets, etc.)
I'll also need address records, so I figure out what I need to track: name, email address, phone number, etc. That's my basic objects right there.
2) What inputs and outputs am I dealing with? What methods would bridge those?
A computer is nothing but input and output. A program inputs and outputs. A method inputs and outputs. If you break your problem down step by step into what goes in and what comes out, you'll often begin to see a solution. I have a List of Addresses (input) and I need emails (output). (Okay technically emailing is probably a side-effect, for all you Functional Programming purists, but we'll say its one of many potential outputs.)
I look in my language documentation for how to email things. I write methods that use those library methods. I need a place to put those methods, so I make a new class and call it "SpamBot3000". I need a way to manage my spam bots so I make another class called "SpamBotManger" and so on. Once you've defined the base problem and started on it, the rest of the classes will usually manifest themselves as necessities.
As a final example, your Tic-Tac-Toe player. My first thought would have been, "I need a board. I can probably use an array of chars for that, holding 'x' 'o' or ' ' as needed." Then I'd put that array in a class, Board. Then I'd add simple methods like "SetSpaceToChar(char c)". Then I'd go "Right, I need a 'Player' class to actually handle whose turn it is and which letter to put. Maybe a 'Game' class to keep score." Then later on I'd think, "You know, letting people put any char into the grid is dangerous. I should switch from char to a specialized type, 'Space' that can only be x o or blank."
In that light, as tiny steps that build on each other, maybe the class structure makes a bit more sense.