(apologies for a unusual long post, but why not?)
I know exactly what you mean, for I had the very same problem three years ago. I started playing with LEGO 55 years ago, when I was 5 years old, and bought and collected sets up to 15 years ago. Then, in a stroke of insanity, I fear, I gave it all away to my neighbors son, who was 5 years old at that time. Within a few years, I started buying again, and three years ago the neighbors son saw my new collection, and offered to give back what he had gotten from me. So there I was, with some 100 kilo of LEGO, with no idea what sets might be hidden in there.
First tip: don't try to do it at once. Start with a bucket of 2 or 3 kilo, sort it, catalog it, take a few days off, and start with the next bucket. -smile-
I used 20 boxes to sort a bucket, which seems to work best. Sort in 3 phases: first 10 by category (bricks, plates, slopes, wheels & tires, minifigs & accessories, technic, electric, doors & windows, markers and all the rest. (I'll talk about markers in a minute)
Then take each category and sort by part (bricks 1 x 1, bricks 1 x 2, etc). Then take each part, sort by color, count and add to Rebrickable.
If you have enough boxes you can store all parts that have been added to Rebrickable separately, if not, I would store them by category (bricks by bricks, plates by plates, etc.)
The sorting itself will probably be time consuming, but not difficult (in fact, I find it very relaxing); but the greatest problem is how to find the parts in Rebrickable once you have them sorted out. Common parts are easy enough, but special parts can be a torment, and it sometimes might take a few hours before you find it.
For 70/80ties LEGO Peeron.com is very good if you can't find the part in Rebrickable, otherwise I suggest making a picture and asking here on the forum.
OK, markers. Markers are parts that LEGO used in one single set (or, perhaps, two or three), that can very easily be used to discover which sets are hidden in your collection of loose bricks. Bricks and slopes with printing on them are usually perfect markers, but sometimes minifig torso's and heads work equally well, as do parts that are very different, either in form or in color, like Fabuland tables and such. Keep these thing apart, and once you track them down, and they are only used in a single set, you know for sure that set is in your collection. Additionally, you can use the parts inventory of that particular set to find part numbers of the other parts you probably have.
Finally, try to get a feel for the parts naming system used by Rebrickable and many other LEGO websites. This kind of information, I think, should really be available in FAQ or Help page, but, right now, Rebrickable doesn't have it. For example, a plate has a thickness of 1/3 of a brick, AND it has one or more studs on it. If it has no studs, it is a tile. So this little thingy: https://rebrickable.com/parts/12825/tile-special-1-x-1-with-clip-with-rounded-tips/
os not a plate but a tile. Knowing in which general category a part might occur is usually the best way to find it.
Hope this helps, any other questions, feel free to ask.