I don't get how the titles of their lords are determined. I know that Alred is the Duke of Nothelm, Baldwin is the Earl of ...Something, and Leofric is the Lord of Raegming. Do they decide who gets what title according to the size and wealth of the shire?

Short answer: yes.

Long answer: Some of the titles I'm using are somewhat anachronistic anyway. Dux as a Latin term was in use at this time, but Duke in English was not. "Baron" is a Norman term. We can pretend that I'm using modern English words as translations, if you like.

Alred, Baldwin, and arguably Leofric would probably have been called "Earls" if Sigefrith is taking his miniature kingdom seriously, since they rule "shires". Otherwise they would be "King's Thegns". A "King's Thegn" would have been approximately equivalent to a Norman Baron. A King's Thegn only has one lord: the King. All other thegns have some other lord, such as some earl or King's thegn.

All of our so-called knights would have been called thegn. "Knight" is an old English word (cniht) but at this era it wasn't yet really being used to describe someone who holds land in exchange for military service. That was a thegn.

Since you asked, Alred got (by far) the most and the richest land in Lothere, by virtue of having funded the expedition. He also got the highest title and highest effective rank. I.e. no matter whether he's called an eorl or a þegn, he's the guy who comes right after the King.

Leofric got a huge swath of land mostly because Sigefrith needed someone guarding the eastern end of the valley. He is still called only "Lord Raegiming" (which implies he is not an Earl) but I would guess that given Baldwin's young age, and the fact that Leofric is the Queen's father and the King's oldest friend -- and just Leof's general pushiness and ballsy-ness -- he probably has worked himself up to #3 in the kingdom after Alred.

I also don't get why knights such as Brede, Stein, and Selwyn get Manors, but Sir Malcolm gets a cottage in the middle of nowhere.

Malcolm explained this himself in "Egelric gives Malcolm something to think about":

“And what does Sigefrith intend to do for you?” [Egelric asked.]

“Knight me, of course, and give me land. But he doesn’t want me managing it.”

“He has more important things for you to do.”

“Precisely,” Malcolm grinned proudly.

Malcolm has a nice chunk of land in approximately the same area as young Sigefrith, but he hardly even rides up to see it. Sigefrith just gave it to him for the income. It is not especially well-managed, contrary to what you might expect from Malcolm. He just doesn't have farming in his blood at all.

The house "in the middle of nowhere" was Malcolm's idea. It's not really in the middle of nowhere -- it's in the woods between the old church and young Sigefrith's manor. It's about a ten or fifteen minute walk from the road. That's what he thought Iylaine wanted.

And how did Egelric get a castle when the other knights got manors? I know it's not really his, but still.

Because he is Alred's pet. There's really no other reason. Egelric has done nothing special to deserve it, aside from refusing it, and refusing to be knighted, and generally making himself disagreeable for so long. I wouldn't be the least bit surprised if someone like Selwyn, say, was miffed due to Egelric getting such a smashing castle when Selwyn is the King's cousin and only gets a little brick house in a muddy, underdeveloped farming village.

And someone like Eadred, who has faithfully served Sigefrith for thirteen years, deserves something nicer than a "stone hut I can't stand up straight in, and last time I was out there it lacked a door!" At least compared to what Egelric's getting for having alternated castle-building and maid-banging with disappearing & sulking spells during that time.

And something tells me that when Yware gets home and finds out that (1) his dad gave "his" castle to Britamund, and (2) his dad gave an EVEN BETTER CASTLE to that grouchy parvenu Egelric, he is going to throw a fabulous fit and cry until his eyeliner runs.

It really ain't fair.

And finally... what in God's goat-fondling world are tithings?

That's just the smallest legal division of Anglo-Saxon society. A tithing is a collection of ten households who sort of form a mini-village within a village. Each tithing has an "elected" leader who represents them in village councils and that sort of thing.

The people in the households are legally responsible for each other -- if one of their number commits a crime, they are responsible for making him show up for trial, and even sometimes responsible for paying the fine if it comes to that. Someone from your tithing had to go with you to witness if you wanted to sell a cow or something. And a person who wanted to swear his innocence in a court only needed to produce a few people from his tithing who said he was a good man, and that was that.

It's really hard for us to imagine living in such a system. Your neighbor's good opinion of you was SO important. They knew so much about you and there was so much social pressure for you to behave and get along well with your neighbors. Otherwise you could be shunned, and life could be made really uncomfortable for you.

For example, in the "Fealufeald" tithing of Maedeshamstede -- where the healer Ffraid lives -- Waleram is the tithingman. Ffraid probably needs his protection enough to put up with his occasional advances. Let's hope he doesn't try to blackmail her one of these days. (Crafty Ffraid may have managed to get his daughters as apprentices in order to implicate his family if the truth ever gets out -- preventing him from telling it.)

I do use tithings in my database sort of unofficially to group people into villages as well. For example, I don't know whether the households living inside of the walls of Nothelm keep really count as a "tithing" -- or at least, if they do, whether Alred and his family really make up part of it. But it helps me keep things straight.