I've started following this weight lifting routine and have adjusted my intake of protein to suit. Should I also be eating more calories in general or do I only need to think about cardio for this?
Weight lifting is great for building muscle. Having more muscle mass has been said as a means of increasing your basal metabolism; therefore burning calories:
Strength training has an added benefit for weight loss in addition to just burning calories. It will raise your muscle metabolism during the exercise session and continue for a long time afterward, even days following high-intensity workouts..
In terms of your other questions about calorie intake and nutritional needs. It really depends on your fitness goals. I'll go ahead and make some broad general assumptions.
If you're just starting off and you're looking to lose weight there are zounds approaches and philosophies: limiting caloric/carbohydrate intake, changing the frequency and spacing of meals, etc.
Also, i would recommend reviewing some threads here on this Fitness.SE:
Weight lifting is work. Work requires calories.
Think of it this way: just being alive burns calories.
Being alive and lifting heavy things will burn more calories, because you're doing more work.
Whether or not you should be eating more calories depends on what you're trying to do.
If you're trying to maintain weight, and you've increased your caloric expenditure, you would need to increase your caloric intake to keep pace. If you're trying to lose or gain weight, you'd need to adjust your caloric intake to match your targeted loss/gain pace.