If I wanted to learn a character in SFV (or any fighting game, really), how should I go about discovering new combos (without the use of videos). Should I be looking at frame data?
Frame data isn't exactly necessary - it just speeds up the process of finding combos (and finding block punishes, but this isn't about block punishes).
Frame data is good for linking combos (timing the button presses) - but also it's good to find target combos (very lenient window of frames to combo).
So lets take Ryu for example - lets look at his frames http://wiki.shoryuken.com/Street_Fighter_V/Ryu
One simple combo is bHK - s.LK - SRK. You see that bHK is +4 on hit and s.LK takes 4 frames of start up. This means you have enough time to link bHK into s.LK and cancel it into a SRK. This is how you figure out combos. Frames are also good for not just combos, but for frame traps as well. Frames however can't really show you corner combos or character specific combos so that requires Training Mode experimentation.
So recap - frames only speed up the process of finding combos/setups. It's always possible to just go into training mode and experiment yourself.
FYI: different fighting game uses different frames data tables to read frames. For example: Street Fighter uses the word "start up frames" to tell how many frames it takes to hit a button to have active hitbox frames, whereas a game like Soul Calibur uses "impact" or "i". Like 4 startup frames would be called "i4"