Yep, Brandis is right - it is veryimportant not to overextend yourself, especially in the very beginning! It's more important that you are doing the pose correctly, not that you can stretch as far as the instructor/the person in the video/whatever. The more you practice, the more flexible and strong you will become, so as you progress you'll naturally be able to stretch farther and go longer!
It's hard to say how quickly you'll progress - it completely depends on where you are now (I obviously had a slight advantage after 17 years of dancing!), how often you practice, for how long you practice and even what poses you do. For me, it took about four weeks to totally master the basic poses without falling or losing my balance, and about six months to reach the advanced poses. But even now, after six years of yoga, there are still poses that I can't fully do - dancer gets me almost every time
That being said, if you truly commit, you should see results very quickly; by the end of the first week, you may notice you are already beginning to loosen up.
I am by no means an expert, but if I were starting out like you, I would probably start with 15 minutes a day for the first couple weeks, then add five minutes each week thereafter until I reached 30 minutes a day. While I prefer to practice in the morning, I find I am far more flexible and able at the end of the day, so that's also something to consider. Downward dog, sun salutation, child's pose, warrior, plan and half twist are all good poses to start with. And before you attempt any poses, definitely watch the video a few times - without an instructor there to critique you, you really want to make sure you understand the pose before you attempt it!
As for feeling sore, it's been a long time since I first started, but I honestly can't remember feeling sore. I would say if you are sore, a hot bath/shower and some ibuprofen is probably the best way to go, but I would also double-check how I was doing each pose to make sure I'm performing them correctly. I always do yoga before and after working out as a warm-up and cool-down and I actually find it helps reduce my soreness!
Like I said, I am by no means an expert, but if you have any specific questions feel free to ask