express-session's dependency on cookie-parser has been removed. That message should come up when the cookie isn't available in req.headers.cookie.
Is your app still working, as you would expect?
What version of express are you using?

The app is still working as expected. I'm using express 4.5.1 and express-session 1.6.4

Can you post a gist that reproduces the issue?

I found the issue (I'm relatively new to express). I had not declared req.headers.cookie. I added a line

req.headers.cookie = null;

and that solved the issue. I guess it was not able to access it because it didn't exist. Thanks for your time.

Its strange that req.headers.cookie = null; solves your issue. the deprecated message should only show up if the cookie is not available at req.headers.cookie, but was available in req.cookies, or req.signedCookies.

Here's the relevant snippet from my app.js. As I said I'm new to express so I may have a glaring mistake I just don't have the intuition to catch.

app.use(function(req, res, next) {
    req.db = db.db;
    req.encoder = new Encoder('entity');
    req.session = null;
    req.headers.cookie = null;
    next();
});

app.use(partials());
app.use(cookieParser());
app.use(session({
    secret: ''+new Date().getTime(),
    cookie: {secure: false},
    resave: true,
    saveUninitialized: true
}));

app.set('port', process.env.PORT || defaultPort);
app.set('views', path.join(__dirname, 'views'));
app.set('view engine', 'ejs');
app.use(logger('dev'));
app.use(bodyParser.json());
app.use(bodyParser.urlencoded({extended: 'false'}));
app.use(express.static('public'));
app.use(express.static(path.join(__dirname, 'public')));

You shouldn't be doing anything to req.session, or req.headers.cookie directly.
You should be able to remove the cookieParser() middleware. Unless you need is for something else, and then you can put it after the session middleware.

The warning is because your secret is ''+new Date().getTime(), so it is different every time you restart the server and it's confusing the internals of this module. Your secret needs to be static. Also, remove app.use(cookieParser());

Its strange that req.headers.cookie = null; solves your issue

@joewagner it made the issue so away because it removed the cookies, essentially, so the module was no longer confused from having an invalid secret.

Thanks for the help!